Jumping Numbers in Java
A number N is referred to as a jumping number if there is an absolute difference of 1 between any two of its adjacent digits. Be aware that the number 0 is not regarded as a 1, nor is the difference between 9 and 0. For this reason, a single digit number is a jumping number.
Example 1:
Input:
int num = 54345
Output:
The given number is a jumping number.
Explanation:
The given number is 54345. Perform the difference between the digits of the given number, i.e. ( 5 - 4 = 1; 4 - 3 = 1; 3 - 4 = -1; 4 - 5 = -1). Since the adjacent difference is -1 and 1 between the digits, the given number is a Jumping Number.
Example 2:
Input:
int num = 8
Output:
The given number is a jumping number.
Explanation:
The given number is 8, which is a single-digit number. By default, one-digit numbers are jumping numbers, so the given number is a jumping number.
Example 3:
Input:
int num = 3465
Output:
The given number is not a jumping number.
Explanation:
The given number is 3465. Perform the difference between the digits of the given number, i.e. (3 - 4 = -1; 4 - 6 = -2; 6 - 5 = 1). The adjacent difference between the digits is not 1 or -1. Hence, the given number is not a jumping number.
Approach: Naïve Approach
Step 1: Start by reading or initializing the number N.
Step 2: Go through the integers 0 through N iteratively.
Step 3: Iterate through the digits of each number.
Step 3.1: Determine whether there is a one-digit difference between the previous and current digits.
Step 4: If every digit in the current integer differs by one, add the integer to the list of jumping numbers.
Implementation:
FileName: JumpingNumber.java
import java.util.*;
import java.io.*;
public class JumpingNumber
{
public static void main(String args[])
{
int diff = 0;
boolean flag = true;
int n = 54345;
while(n != 0)
{
// finds the last digit in the given number.
int d1 = n % 10;
// The final digit is removed.
n = n/10;
if(n != 0)
{
// If the preceding criteria are satisfied, the second last digit of the number is determined.
int d2 = n % 10;
// To determine the absolute value, subtract the digits.
//then determines if the difference between two consecutive digits is equal to one.
if(Math.abs(d1 - d2) != 1)
{
// Set the flag to false if the difference is less than or equal to 1.
flag = false;
break;
}
}
}
if(flag)
System.out.println("The given number is a jumping number.");
else
System.out.println("The given number is not a jumping number.");
}
}
Output:
The given number is a jumping number.
Complexity Analysis:
The time complexity of the above program is O(logN), where N represents the
given input.
Print Every Jumping Number in a Specific Range
Printing every jumping number within a specified range can be done in two ways:
- By Using DFS
- By Using BFS
By using DFS:
In DFS, all jumping numbers are printed directly rather than having each integer checked. To do this, we begin with the initial jumping number, which is 0, and add a new digit to it so that the difference between the current digit and the previous digit is 1.
Keep in consideration that the only possible subsequent digit, 1 (which corresponds to the next jumping number), will occur if the preceding digit is 0. In a similar vein, digit 9 can only have digit 8 as the following digit, not 10. However, there will always be two options for the next digits (one greater than it, and one less) for the numbers 1 through 8.
The process continues the previously mentioned procedure using 1. The two alternatives we have left for the following digit are 2 and 0, which will result in the two new jumping numbers, 12 and 10. We consider numbers to be the nodes present in the graph in this method.
Algorithm:
Step 1: Assuming the numbers represent the nodes of the graph, the preceding method can be applied in execution.
Step 2: Apply DFS to the graph, beginning at node '0'.
Step 3: The fundamental Condition is that the traverse for that node should end, and we should return if the created node or number is larger than N.
Step 4: If the number is less than N, add it to the jumping list together with the current node.
Step 5: At this point, in order to move from one node to the next, add digits to the one that is now active so that the number that is generated after it is also a jumping number. Then, call DFS on the subsequent node recursively.
Step 6: Repeat the above technique using the remaining integers 2–9 as the beginning nodes if we want to generate all the jumping numbers.
Step 7: Sort the jumping numbers list at the end and give the same list back.
Implementation:
FileName: JumpingNumberDFS.java
import java.util.*;
import java.io.*;
public class JumpingNumberDFS
{
public static void main(String[] args)
{
int n = 104;
Set<Integer> range= new HashSet<>();
for(int i=0; i<10; i++)
{
DFSJumping(n, range, i);
}
List<Integer> result = new ArrayList<>(range);
//sorts the range of elements of an array
Collections.sort(result);
System.out.println("The jumping numbers upto the given input number are :" + result);
}
static void DFSJumping(int n, Set<Integer> result, int temp)
{
if(temp > n)
return;
if(!result.add(temp))
return;
if(temp%10 == 0)
{
DFSJumping(n, result, temp * 10 + 1);
}
else if(temp%10 == 9)
{
DFSJumping(n, result, temp * 10 + 8);
}
else
{
DFSJumping(n, result, temp * 10 + temp%10 - 1);
DFSJumping(n, result, temp * 10 + temp%10 + 1);
}
}
}
Output:
The jumping numbers upto the given input number are :[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98, 101]
Complexity Analysis:
The time complexity for the above program is O(k), where k represents the total number of jumping numbers up to the given number, and the space complexity is O(len(N)).
By using BFS:
The methodology is similar to DFS. However, we can choose to create the graph using BFS instead of DFS.
Algorithm:
Step 1: Create an empty queue.
Step 2: Place '0', the initial node, in the queue.
Step 3: Carry out the previous actions until the queue remains empty
Step 3.1: Select the top node in the queue to serve as the active node.
Step 3.2: The current node (number) is added to the list of jumping numbers in this step if it is less than or equal to N.
Step 3.3: Next, create the next node by adding digits to the one that is now formed so that the subsequent number (node) created is likewise a jumping number as well as insert the number into the line.
Step 3.4: Proceed to the next queue node if not.
Step 4: Use the remaining integers from 2 to 9 as the beginning nodes in the previously mentioned method to generate all the jumping numbers.
Step 5: Sort the jumping numbers list at the end and give the same list back.
Implementation:
FileName: JumpingNumberBFS.java
import java.util.*;
import java.lang.*;
import java.io.*;
public class JumpingNumberBFS
{
public void Jumping(int x, int n)
{
Queue<Integer> queue = new LinkedList<Integer>();
// The element is inserted into the queue.
queue.add(n);
//Do BFS beginning at i
// execute a while loop until the queue is empty;
while (!queue.isEmpty())
{
// The head of the queue is obtained using the Queue class's peek() method; it is not removed.
n = queue.peek();
// The head of the queue can be obtained and removed using the Queue class's poll() method.
queue.poll();
// continues until the condition is no longer true.
if (n <= x)
{
System.out.print(n + " ");
int lastdigit = n % 10;
// determines if the last digit is zero or not
if (lastdigit == 0)
{
// only add the next digit if the last digit is 0.
queue.add((n * 10) + (lastdigit + 1));
}
// verifies whether or not the final digit is 9
else if (lastdigit == 9)
{
// add only the preceding digit if the last digit is 9.
queue.add((n * 10) + (lastdigit - 1));
}
// carries out if the final digit is not either 0 or 9.
//Add the preceding and next digits
else
{
// Adds the preceding number to the queue
queue.add((n * 10) + (lastdigit - 1));
// adds the next number
queue.add((n * 10) + (lastdigit + 1));
}
}
}
}
// displays every jumping number that is either equal to or less than x
public void JumpingNumberPrinting(int x)
{
System.out.println("The jumping numbers upto the given input number are : ");
System.out.print("0 ");
for (int i = 1; i <= 9 && i <= x; i++)
{
// Invoking a function created by the user to determine whether the provided number is jumping or not
this.Jumping(x, i);
}
}
public static void main(String args[])
{
int x = 500;
JumpingNumberBFS bfsjn = new JumpingNumberBFS ();
bfsjn.JumpingNumberPrinting(x);
}
}
Output:
The jumping numbers upto the given input number are :
0 1 10 12 101 121 123 2 21 23 210 212 232 234 3 32 34 321 323 343 345 4 43 45 432 434 454 456 5 54 56 6 65 67 7 76 78 8 87 89 9 98
Complexity Analysis:
The time complexity for the above program is O(k), where k represents the total number of jumping numbers up to the given number, and the space complexity is O(1).