Given two integers N and K, the task is to generate all positive integers with length N having an absolute difference of adjacent digits equal to K.
Examples:
Input: N = 4, K = 8
Output: 1919, 8080, 9191
Explanation:
The absolute difference between every consecutive digit of each number is 8.
For Example: 8080 (abs(8-0) = 8, abs(0-8) = 8)Input: N = 2, K = 2
Output: 13, 24, 20, 35, 31, 46, 42, 57, 53, 68, 64, 79, 75, 86, 97
Explanation:
The absolute difference between every consecutive digit of each number is 1.
Approach: The idea is to use Backtracking. Iterate over digits [1, 9] and for each digit from the N-digit number having a difference of absolute digit as K using recursion. Below are the steps:
1. Create a vector ans[] to store all the resulting numbers and recursively iterate from 1 to 9 to generate numbers starting from each digit. Below are the cases:
- Base Case: For all integers of a single length, that is, N = 1, add them to ans[].
- Recursive Call: If adding digit K to the numbers to one’s digit doesn’t exceed 9, then recursively call by decreasing the N and update num to (10*num + num%10 + K) as shown below:
if(num % 10 + K ? 9) {
recursive_function(10 * num + (num % 10 + K), K, N – 1, and);
}
- If the value of K is non-zero after all the recursive call and if num % 10 >= K, then again recursively call by decreasing the N and update num to (10*num + num%10 – K) as:
recursive_function(10 * num + num % 10 – K, K, N – 1, ans);
2. After all the above steps print the numbers stored in ans[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that recursively finds the// possible numbers and append into ansvoid checkUntil(int num, int K, int N, vector<int>& ans){ // Base Case if (N == 1) { ans.push_back(num); return; } // Check the sum of last digit and k // less than or equal to 9 or not if ((num % 10 + K) <= 9) checkUntil(10 * num + (num % 10 + K), K, N - 1, ans); // If k==0, then subtraction and // addition does not make any // difference // Hence, subtraction is skipped if (K) { if ((num % 10 - K) >= 0) checkUntil(10 * num + num % 10 - K, K, N - 1, ans); }}// Function to call checkUntil function// for every integer from 1 to 9void check(int K, int N, vector<int>& ans){ // check_util function recursively // store all numbers starting from i for (int i = 1; i <= 9; i++) { checkUntil(i, K, N, ans); }}// Function to print the all numbers// which satisfy the conditionsvoid print(vector<int>& ans){ for (int i = 0; i < ans.size(); i++) { cout << ans[i] << ", "; }}// Driver Codeint main(){ // Given N and K int N = 4, K = 8; // To store the result vector<int> ans; // Function Call check(K, N, ans); // Print Resultant Numbers print(ans); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{ // Function that recursively finds the // possible numbers and append into ans static void checkUntil(int num, int K, int N, Vector<Integer> ans) { // Base Case if (N == 1) { ans.add(num); return; } // Check the sum of last digit and k // less than or equal to 9 or not if ((num % 10 + K) <= 9) checkUntil(10 * num + (num % 10 + K), K, N - 1, ans); // If k==0, then subtraction and // addition does not make any // difference // Hence, subtraction is skipped if (K > 0) { if ((num % 10 - K) >= 0) checkUntil(10 * num + num % 10 - K, K, N - 1, ans); } } // Function to call checkUntil function // for every integer from 1 to 9 static void check(int K, int N, Vector<Integer> ans) { // check_util function recursively // store all numbers starting from i for (int i = 1; i <= 9; i++) { checkUntil(i, K, N, ans); } } // Function to print the all numbers // which satisfy the conditions static void print(Vector<Integer> ans) { for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + ", "); } } // Driver Code public static void main(String[] args) { // Given N and K int N = 4, K = 8; // To store the result Vector<Integer> ans = new Vector<Integer>();; // Function Call check(K, N, ans); // Print Resultant Numbers print(ans); }}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function that recursively finds the# possible numbers and append into ansdef checkUntil(num, K, N, ans): # Base Case if (N == 1): ans.append(num) return # Check the sum of last digit and k # less than or equal to 9 or not if ((num % 10 + K) <= 9): checkUntil(10 * num + (num % 10 + K), K, N - 1, ans) # If k==0, then subtraction and # addition does not make any # difference # Hence, subtraction is skipped if (K): if ((num % 10 - K) >= 0): checkUntil(10 * num + num % 10 - K, K, N - 1, ans) # Function to call checkUntil function# for every integer from 1 to 9def check(K, N, ans): # check_util function recursively # store all numbers starting from i for i in range(1, 10): checkUntil(i, K, N, ans)# Function to print the all numbers# which satisfy the conditionsdef print_list(ans): for i in range(len(ans)): print(ans[i], end = ", ")# Driver Codeif __name__ == "__main__": # Given N and K N = 4 K = 8; # To store the result ans = [] # Function call check(K, N, ans) # Print resultant numbers print_list(ans)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function that recursively finds the// possible numbers and append into ansstatic void checkUntil(int num, int K, int N, List<int> ans){ // Base Case if (N == 1) { ans.Add(num); return; } // Check the sum of last digit and k // less than or equal to 9 or not if ((num % 10 + K) <= 9) checkUntil(10 * num + (num % 10 + K), K, N - 1, ans); // If k==0, then subtraction and // addition does not make any // difference // Hence, subtraction is skipped if (K > 0) { if ((num % 10 - K) >= 0) checkUntil(10 * num + num % 10 - K, K, N - 1, ans); }}// Function to call checkUntil function// for every integer from 1 to 9static void check(int K, int N, List<int> ans){ // check_util function recursively // store all numbers starting from i for(int i = 1; i <= 9; i++) { checkUntil(i, K, N, ans); }}// Function to print the all numbers// which satisfy the conditionsstatic void print(List<int> ans){ for(int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + ", "); }}// Driver Codepublic static void Main(String[] args){ // Given N and K int N = 4, K = 8; // To store the result List<int> ans = new List<int>();; // Function call check(K, N, ans); // Print Resultant Numbers print(ans);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to implement// the above approach // Function that recursively finds the // possible numbers and append into ans function checkUntil(num, K, N, ans) { // Base Case if (N == 1) { ans.push(num); return; } // Check the sum of last digit and k // less than or equal to 9 or not if ((num % 10 + K) <= 9) checkUntil(10 * num + (num % 10 + K), K, N - 1, ans); // If k==0, then subtraction and // addition does not make any // difference // Hence, subtraction is skipped if (K > 0) { if ((num % 10 - K) >= 0) checkUntil(10 * num + num % 10 - K, K, N - 1, ans); } } // Function to call checkUntil function // for every integer from 1 to 9 function check(K, N, ans) { // check_util function recursively // store all numbers starting from i for (let i = 1; i <= 9; i++) { checkUntil(i, K, N, ans); } } // Function to print the all numbers // which satisfy the conditions function print( ans) { for (let i = 0; i < ans.length; i++) { document.write(ans[i] + ", "); } }// Driver Code // Given N and K let N = 4, K = 8; // To store the result let ans = [] // Function Call check(K, N, ans); // Print Resultant Numbers print(ans); </script> |
Output:
1919, 8080, 9191,
Time Complexity: O(2N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
