Given a number N, the task is to find the Nth number which has an absolute difference of 1 between every pair of its adjacent digits.
Examples:
Input : N = 5
Output : 5
Explanation:
The first 5 such numbers are 1,2,3,4 and 5.
Input : N = 15
Output : 23
Explanation:
The first 15 such numbers are 1,2,3,4,5,6,7,8,9,10,11,12,21,22 and 23.
Approach: In order to solve this problem we are using the Queue data structure.
- Prepare an empty Queue, and Enqueue all integers 1 to 9 in increasing order.
- Now perform the following operation N times.
- Dequeue and store in array arr which stores ith number of required type in arr[i].
- If (arr[i] % 10 != 0), then enqueue 10 * arr[i] + (arr[i] % 10) – 1.
- Enqueue 10 * arr[i] + (arr[i] % 10).
- If (arr[i] % 10 != 9), then enqueue 10 * arr[i] + (arr[i] % 10) + 1.
- Return arr[N] as the answer.
Below is the implementation of the given approach:
C++
// C++ Program to find Nth number with// absolute difference between all // adjacent digits at most 1.#include <bits/stdc++.h>using namespace std;// Return Nth number with// absolute difference between all // adjacent digits at most 1.void findNthNumber(int N){ // To store all such numbers long long arr[N + 1]; queue<long long> q; // Enqueue all integers from 1 to 9 // in increasing order. for (int i = 1; i <= 9; i++) q.push(i); // Perform the operation N times so that // we can get all such N numbers. for (int i = 1; i <= N; i++) { // Store the front element of queue, // in array and pop it from queue. arr[i] = q.front(); q.pop(); // If the last digit of dequeued integer is // not 0, then enqueue the next such number. if (arr[i] % 10 != 0) q.push(arr[i] * 10 + arr[i] % 10 - 1); // Enqueue the next such number q.push(arr[i] * 10 + arr[i] % 10); // If the last digit of dequeued integer is // not 9, then enqueue the next such number. if (arr[i] % 10 != 9) q.push(arr[i] * 10 + arr[i] % 10 + 1); } cout<<arr[N]<<endl;}// Driver Codeint main(){ int N = 21; findNthNumber(N); return 0;} |
Java
// Java program to find Nth number with// absolute difference between all // adjacent digits at most 1.import java.util.*;class GFG{// Return Nth number with// absolute difference between all // adjacent digits at most 1.static void findNthNumber(int N){ // To store all such numbers int []arr = new int[N + 1]; Queue<Integer> q = new LinkedList<>(); // Enqueue all integers from 1 to 9 // in increasing order. for(int i = 1; i <= 9; i++) q.add(i); // Perform the operation N times so // that we can get all such N numbers. for(int i = 1; i <= N; i++) { // Store the front element of queue, // in array and pop it from queue. arr[i] = q.peek(); q.remove(); // If the last digit of dequeued // integer is not 0, then enqueue // the next such number. if (arr[i] % 10 != 0) q.add(arr[i] * 10 + arr[i] % 10 - 1); // Enqueue the next such number q.add(arr[i] * 10 + arr[i] % 10); // If the last digit of dequeued // integer is not 9, then enqueue // the next such number. if (arr[i] % 10 != 9) q.add(arr[i] * 10 + arr[i] % 10 + 1); } System.out.println(arr[N]);}// Driver Codepublic static void main(String[] args){ int N = 21; findNthNumber(N);}}// This code is contributed by Amit Katiyar |
Python3
# Python 3 Program to find Nth number with# absolute difference between all # adjacent digits at most 1.# Return Nth number with# absolute difference between all # adjacent digits at most 1.def findNthNumber(N): # To store all such numbers arr = [0 for i in range(N + 1)] q = [] # Enqueue all integers from 1 to 9 # in increasing order. for i in range(1, 10, 1): q.append(i) # Perform the operation N times so that # we can get all such N numbers. for i in range(1, N+1, 1): # Store the front element of queue, # in array and pop it from queue. arr[i] = q[0] q.remove(q[0]) # If the last digit of dequeued integer is # not 0, then enqueue the next such number. if (arr[i] % 10 != 0): q.append(arr[i] * 10 + arr[i] % 10 - 1) # Enqueue the next such number q.append(arr[i] * 10 + arr[i] % 10) # If the last digit of dequeued integer is # not 9, then enqueue the next such number. if (arr[i] % 10 != 9): q.append(arr[i] * 10 + arr[i] % 10 + 1) print(arr[N])# Driver Codeif __name__ == '__main__': N = 21 findNthNumber(N)# This code is contributed by Samarth |
C#
// C# program to find Nth number with// absolute difference between all // adjacent digits at most 1.using System;using System.Collections.Generic;class GFG{// Return Nth number with// absolute difference between all // adjacent digits at most 1.static void findNthNumber(int N){ // To store all such numbers int []arr = new int[N + 1]; Queue<int> q = new Queue<int>(); // Enqueue all integers from 1 to 9 // in increasing order. for(int i = 1; i <= 9; i++) q.Enqueue(i); // Perform the operation N times so // that we can get all such N numbers. for(int i = 1; i <= N; i++) { // Store the front element of queue, // in array and pop it from queue. arr[i] = q.Peek(); q.Dequeue(); // If the last digit of dequeued // integer is not 0, then enqueue // the next such number. if (arr[i] % 10 != 0) q.Enqueue(arr[i] * 10 + arr[i] % 10 - 1); // Enqueue the next such number q.Enqueue(arr[i] * 10 + arr[i] % 10); // If the last digit of dequeued // integer is not 9, then enqueue // the next such number. if (arr[i] % 10 != 9) q.Enqueue(arr[i] * 10 + arr[i] % 10 + 1); } Console.WriteLine(arr[N]);}// Driver Codepublic static void Main(String[] args){ int N = 21; findNthNumber(N);}}// This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript program to find Nth number with // absolute difference between all // adjacent digits at most 1. // Return Nth number with // absolute difference between all // adjacent digits at most 1. function findNthNumber(N) { // To store all such numbers let arr = new Array(N + 1); let q = []; // Enqueue all integers from 1 to 9 // in increasing order. for(let i = 1; i <= 9; i++) q.push(i); // Perform the operation N times so // that we can get all such N numbers. for(let i = 1; i <= N; i++) { // Store the front element of queue, // in array and pop it from queue. arr[i] = q[0]; q.shift(); // If the last digit of dequeued // integer is not 0, then enqueue // the next such number. if (arr[i] % 10 != 0) q.push(arr[i] * 10 + arr[i] % 10 - 1); // Enqueue the next such number q.push(arr[i] * 10 + arr[i] % 10); // If the last digit of dequeued // integer is not 9, then enqueue // the next such number. if (arr[i] % 10 != 9) q.push(arr[i] * 10 + arr[i] % 10 + 1); } document.write(arr[N] + "</br>"); } let N = 21; findNthNumber(N);</script> |
45
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/nth-positive-number-whose-absolute-difference-of-adjacent-digits-is-at-most-1/ […]
… [Trackback]
[…] Read More here on that Topic: geeksforgeeks.org/nth-positive-number-whose-absolute-difference-of-adjacent-digits-is-at-most-1/ […]
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/nth-positive-number-whose-absolute-difference-of-adjacent-digits-is-at-most-1/ […]
… [Trackback]
[…] Read More on on that Topic: geeksforgeeks.org/nth-positive-number-whose-absolute-difference-of-adjacent-digits-is-at-most-1/ […]
… [Trackback]
[…] Here you can find 49334 more Information on that Topic: geeksforgeeks.org/nth-positive-number-whose-absolute-difference-of-adjacent-digits-is-at-most-1/ […]