Approach and Explanation
Absolute difference of adjacent digits is at most 1 means numbers whose difference of adjacent digits is -1, 0, or 1. Such numbers include 1 to 12, 21, 22, 23, 32, 33, 34, and so on. Our task is to find the Nth such digit.
Let us take a small example to understand the problem better.
-
Consider an array arr1 having elements from 1 to 9.
-
To make an array of numbers having a difference of adjacent digits as 0, we simply multiply each digit by ten and add mod ten. This array can be called arr2.
-
To make an array with numbers having differences of adjacent digits as -1, we simply subtract 1 from each element of arr2. We name this array arr3.
-
To make an array of numbers having a difference of adjacent digits as 1, we simply add 1 to each element of arr2. We name this array arr4.
-
The cumulative sorted array formed by arr1, arr2, arr3, and arr4 is a valid solution array.
- For visual reference, the arrays formed are as follows:
Now, to implement this logic, we can follow these steps:
-
Check if the number is less than or equal to 12.
-
If true, then print the number itself. If false, then do the following steps.
-
Create an integer array of size N+1, and a new Queue.
-
Enqueue the digits 1 to 9 in the queue.
-
Declare a for loop from 1 to N.
- Add the number at the bottom of the queue at arr[i] and dequeue.
- In a temporary variable (say smallAns) find and store the value of arr[i]*10 + arr[i]%10. .
- If arr[i] %10 != 0, enqueue smallAns+1. (This will help make arr3, as seen in the explanation above).
- Enqueue smallAns. (This will help make arr2, as seen in the explanation above).
-
If arr[i] %10 != 9, enqueue smallAns-1. (This will help make arr4, as seen in the explanation above).
- Once the loop is complete, print arr[N].
The java implementation of the given logic is given below. It is recommended to write the code first before moving to the solution code.
Java Implementation
import java.util.Queue;
import java.util.LinkedList;
public class NthPosNum{
static void findNNumber(int nDigit)
{
if(nDigit <= 12){
System.out.println(nDigit);
return;
}
int[] posArr = new int[nDigit + 1];
int smallAns;
Queue<Integer> queue = new LinkedList<>();
for(int i = 1; i <= 9; i++)
queue.add(i);
for(int i = 1; i <= nDigit; i++)
{
posArr[i] = queue.peek();
queue.remove();
smallAns = posArr[i] * 10 + posArr[i] % 10;
if (posArr[i] % 10 != 0){
queue.add(smallAns - 1);
}
queue.add(smallAns);
if (posArr[i] % 10 != 9) {
queue.add(smallAns + 1);
}
}
System.out.println(posArr[nDigit]);
}
public static void main(String[] args)
{
int nDigit = 32;
findNNumber(nDigit);
}
}
OUTPUT
88
Complexities
Time Complexity
In the given implementation, if the value of nDigit is less than 12, then it takes O(1) time to compute. Else, we make nDigit computations to fill our array. Thus time complexity is, T(n) = O(N), where N is the Nth digit to be found.
Space Complexity
In the given implementation, if the value of nDigit is less than 12, then it takes O(1) space to compute. Else, we create an array of size nDigit to store all the numbers whose absolute difference is at most 1. Thus, Space Complexity = O(N), where N is the Nth digit to be found.
Frequently Asked Questions
What do you mean by the absolute difference of adjacent digits is at most 1?
An absolute difference of at most 1 means that the mod of difference of the two numbers should be one. The difference can be -1, 0, or 1. Thus digits such as 1, 22, 234, 345, and so on can be considered such numbers are the difference of the digits is either 0, 1, or -1.
What is the difference between a Stack and a Queue?
A Stack is a data structure following the LIFO (Last In First Out) order. A Queue is a data structure following the FIFO (First In First Out) order. To get a deeper idea of the two, please click Stack and Queue to find various articles covering all the concepts related to Stack and Queue.
Conclusion
To summarize the article, we discussed the nth positive number whose absolute difference of adjacent digits is at most 1 problem in depth. We saw the problem statement, an example, and an approach. We also saw the Java implementation of the approach along with the time and space complexities. We summed up the article with a few FAQs.
Improve your coding skills by practicing various problems of various difficulty levels on our Coding Ninjas Studio.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Coding!
84+ registered 