Create account

DEV Community

Rohith V

Posted on Jun 9, 2021

Jumping Numbers

#java #algorithms #programming #tutorial

Problem Statement

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 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

Test Cases

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.

Our 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 and Space Complexity

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

Constraints

1 <= X <= 10^9

Approach

Here we will be given a number say n, we need to find a way to get the maximum jumping number less than or equal to n.

For example, if our n = 50, the jumping numbers are
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, 43, 45]

So from this list, we can find that 45 is the largest jumping number which is <= 50.
Therefore we need to design an algorithm so that we can get the list of these jumping numbers and find the maximum from it easily.

Here our search space is from 0 to 50. 0 - 10 is always included as jumping numbers. So for any input n <= 10, we can just return that number which will be the desired answer.

The rest of the numbers can be found out using a Breadth First Search Algorithm or Depth First Search Algorithm.
Here I am going to say about the depth first search algorithm.

Algorithm

for i in range of 0 to 10, do a bfs search.

List<Integer> results = new ArrayList<>();
for (int i=0; i<10 && i <= n; i++) {
        bfs(n, i, results);
}

Now inside the bfs, we start by creating a queue as usual and store the current i inside the queue.
while the queue is not empty, we continue with the following steps :
- poll out the current number from the queue.
- check whether the current number <= input, if yes add it into the list
- find the last digit of the current number by doing %10
- if the last digit is 0, there won't be any number that differ by 1 from the left side, so add (current number * 10) + lastdigit + 1 into the queue.
- if the last digit is 9, there won't be any number that differ by 1 from the right side, so add (current number * 10) + lastdigit - 1 into the queue.
- for all other last digits, there can be one number from the left and one from the right. ie (current number * 10) + lastdigit - 1 and (current number * 10) + lastdigit + 1 into the queue.

static void bfs(long n, int i, List<Integer> results) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            i = queue.poll();
            if (i <= n) {
                results.add(i);
                int lastDigit = i % 10;
                if (lastDigit == 0) {
                    queue.add((i * 10) + (lastDigit + 1));
                }
                else if (lastDigit == 9) {
                    queue.add((i * 10) + (lastDigit - 1));
                }
                else {
                    queue.add((i * 10) + (lastDigit + 1));
                    queue.add((i * 10) + (lastDigit - 1));
                }
            }
        }
    }

now our list will be populated with all the jumping numbers, all we have to do now is find the maximum from the list and return the answer.

int max = Integer.MIN_VALUE;
for (int number : results) {
        max = Math.max(number, max);
}
return max;

Complete Code

class Solution {

    static void bfs(long n, int i, List<Integer> results) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        while (!queue.isEmpty()) {
            i = queue.poll();
            if (i <= n) {
                results.add(i);
                int lastDigit = i % 10;
                if (lastDigit == 0) {
                    queue.add((i * 10) + (lastDigit + 1));
                }
                else if (lastDigit == 9) {
                    queue.add((i * 10) + (lastDigit - 1));
                }
                else {
                    queue.add((i * 10) + (lastDigit + 1));
                    queue.add((i * 10) + (lastDigit - 1));
                }
            }
        }
    }

    static long jumpingNums(long n) {
        // code here
        if (n <= 10)
            return n;
        List<Integer> results = new ArrayList<>();
        for (int i=0; i<10 && i <= n; i++) {
            bfs(n, i, results);
        }
        int max = Integer.MIN_VALUE;
        for (int number : results) {
            max = Math.max(number, max);
        }
        return max;
    }
}