Jumping Numbers ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

ASK in AMAZON




Medium

Given a positive number X. Find the largest Jumping Number smaller than or equal to X. 
Jumping Number: A number is called Jumping Number if all adjacent digits in it differ by only 1. All single digit numbers are considered as Jumping Numbers. For example 78987 and 4343456 are Jumping numbers but 796 and 89098 are not.

 

Example 1:

Input:
X = 10
Output:
10
Explanation:
10 is the largest Jumping Number
possible for X = 10.

Example 2:

Input:
X = 50
Output:
45
Explanation:
45 is the largest Jumping Number
possible for X = 50.

 

Your Task:
You don't need to read input or print anything. Your task is to complete the function jumpingNums() which takes an Integer X as input and returns the largest Jumping Number less than or equal to X.

 

Expected Time Complexity: O(k), where k is no of jumping numbers

Constraints:
1 <= X <= 109
Expected Auxiliary Space: O(k), where k is no of jumping numbers

Code:

#include <bits/stdc++.h>

using namespace std;


// Prints all jumping numbers smaller than or equal to x starting

// with 'num'. It mainly does BFS starting from 'num'.

void bfs(int x, int num)

{

    // Create a queue and enqueue 'i' to it

    queue<int> q;

    q.push(num);


    // Do BFS starting from i

    while (!q.empty()) {

        num = q.front();

        q.pop();


        if (num <= x) {

            cout << num << " ";

            int last_dig = num % 10;

// If last digit is 0, append next digit only

            if (last_dig == 0)

                q.push((num * 10) + (last_dig + 1));


            // If last digit is 9, append previous digit only

            else if (last_dig == 9)

                q.push((num * 10) + (last_dig - 1));


            // If last digit is neighter 0 nor 9, append both

            // previous and next digits

            else {

                q.push((num * 10) + (last_dig - 1));

                q.push((num * 10) + (last_dig + 1));

            }

        }

    }

}

// Prints all jumping numbers smaller than or equal to

// a positive number x

void printJumping(int x)

{

    cout << 0 << " ";

    for (int i = 1; i <= 9 && i <= x; i++)

        bfs(x, i);

}


// Driver program

int main()

{

    int x = 40;

    printJumping(x);

    return 0;

}


 






Previous
Next Post »