Given integers T, A, and B, the task for this problem is to find numbers in the range [A, B] such that the adjacent digits of the number are different and the sum of digits is equal to T. ( A ? B ? 1018)
Examples:
Input: T = 5, A = 1, B = 100
Output: 6
Explanation: 5, 14, 23, 32, 41, and 50 are valid integers that are in between the range 1 to 100 and have the sum of digits 5 along with adjacent digits different.Input: T = 5, A = 1, B = 100000000
Output: 74
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(18N), Where N is the number of digits from 0 to 9.
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
- dp[i][j][k][sum] represents numbers with i digits, j is the tight condition pointer, k is the last digit taken and the sum is digit sum till i.
- It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly.
- So the idea is to store the value of each state. This can be done using by the store the value of a state and whenever the function is called, returning the stored value without computing again.
Follow the steps below to solve the problem:
- Create a recursive function that takes four parameters i represents a position to be filled, j represents the tight condition pointer, k represents the last digit taken and sum represents the total sum of digits.
- Call the recursive function for choosing all digits from 0 to 9.
- Base case if N size digit formed and the sum of digits equal to T return 1 else return 0.
- Create a 4d array dp[21][21][10][190] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j][k][sum].
- If the answer for a particular state is already computed then just return dp[i][j][k][sum].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// Dp table initialized with -1int dp[21][21][10][190];// Recursive Function to find numbers// in the range A to B such that adjacent// digits are different and their sum is// equal to Tint recur(int i, int j, int k, int sum, int T, string& a){ // Base case if (i == a.size()) { // If current sum is equal to T if (sum == T) return 1; // If not equal to T else return 0; } // If answer for current state is already // calculated then just // return dp[i][j][k][sum] if (dp[i][j][k][sum] != -1) return dp[i][j][k][sum]; // Answer initialized with zero int ans = 0; // Choosing first value if (i == 0) { // Iterating from 0 to maxvalue // of digit current position // can have for (int l = 0; l <= (int)(a[j] - 48); l++) { // l is maximum value of digit if (l == (int)(a[j] - 48)) { // Calling recursive function // for selecting last max digit // for current position ans += recur(i + 1, j + 1, l, sum + l, T, a); } else // Calling recursive function // for selecting l as current // digit and its not max digit ans += recur(i + 1, j, l, sum + l, T, a); } } else { // Digits taken till now were // all zero if (sum == 0) { // All digits can be possible // from 0 to 9 for (int l = 0; l <= 9; l++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, j, l, sum + l, T, a); } } // Already non zero digits are taken else { // Iterating from 0 to 9 for (int l = 0; l <= 9; l++) { // If max digit was taken // last time if (j == i) { // If current digit // is different if (l <= (int)(a[j] - 48) and l != k) { // max digit taken calling // recursive function if (l == (int)(a[j] - 48)) ans += recur(i + 1, j + 1, l, sum + l, T, a); // Calling recursive // function for non // max digit else ans += recur(i + 1, j, l, sum + l, T, a); } } // If max digit was not taken else if (l != k) ans += recur(i + 1, j, l, sum + l, T, a); } } } // Save and return dp value return dp[i][j][k][sum] = ans;}// Function to find numbers// in the range A to B such that adjacent// digits are different and their sum is// equal to Tint countInRange(int T, int A, int B){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); A--; string L = to_string(A), R = to_string(B); // Numbers with sum of digits T from // 1 to L - 1 int ans1 = recur(0, 0, 0, 0, T, L); // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // Numbers with sum of digits T in // the range 1 to R int ans2 = recur(0, 0, 0, 0, T, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1;}// Driver Codeint main(){ // Input 1 int T = 5, A = 1, B = 100; // Function Call cout << countInRange(T, A, B) << endl; // Input 2 int T1 = 5, A1 = 1, B1 = 100000000; // Function Call cout << countInRange(T1, A1, B1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { static final int MOD = (int)1e9 + 7; static int dp[][][][]; // Dp table initialized with -1 static void memset(int[][][][] dp) { for (int i = 0; i < 21; i++) { dp[i] = new int[21][10][190]; for (int j = 0; j < 21; j++) { for (int k = 0; k < 10; k++) { Arrays.fill(dp[i][j][k], -1); } } } } // Recursive Function to find numbers in the range A to // B such that adjacent digits are different and their // sum is equal to T static int recur(int i, int j, int k, int sum, int T, char a[]) { // Base case if (i == a.length) { // If current sum is equal to T if (sum == T) { return 1; } // If not equal to T else { return 0; } } // If answer for current state is already calculated // then just return dp[i][j][k][sum] if (dp[i][j][k][sum] != -1) { return dp[i][j][k][sum]; } // Answer initialized with zero int ans = 0; // Choosing first value if (i == 0) { // Iterating from 0 to maxvalue // of digit current position // can have for (int l = 0; l <= (a[j] - '0'); l++) { // l is maximum value of digit if (l == (a[j] - '0')) { // Calling recursive function // for selecting last max digit // for current position ans += recur(i + 1, j + 1, l, sum + l, T, a); } else { // Calling recursive function // for selecting l as current // digit and its not max digit ans += recur(i + 1, j, l, sum + l, T, a); } } } else { // Digits taken till now were // all zero if (sum == 0) { // All digits can be possible // from 0 to 9 for (int l = 0; l <= 9; l++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, j, l, sum + l, T, a); } } // Already non zero digits are taken else { // Iterating from 0 to 9 for (int l = 0; l <= 9; l++) { // If max digit was taken // last time if (j == i) { // If current digit // is different if (l <= (a[j] - '0') && l != k) { // max digit taken calling // recursive function if (l == (a[j] - '0')) { ans += recur(i + 1, j + 1, l, sum + l, T, a); } // Calling recursive // function for non // max digit else { ans += recur(i + 1, j, l, sum + l, T, a); } } } // If max digit was not taken else if (l != k) { ans += recur(i + 1, j, l, sum + l, T, a); } } } } // Save and return dp value return dp[i][j][k][sum] = ans; } // Function to find numbers // in the range A to B such that adjacent // digits are different and their sum is // equal to T static int countInRange(int T, int A, int B) { dp = new int[21][21][10][190]; // Initializing dp array with - 1 memset(dp); String L = Integer.toString(A - 1); String R = Integer.toString(B); // Numbers with sum of digits T from // 1 to L - 1 int ans1 = recur(0, 0, 0, 0, T, L.toCharArray()); // Initializing dp array with - 1 memset(dp); // Numbers with sum of digits T in // the range 1 to R int ans2 = recur(0, 0, 0, 0, T, R.toCharArray()); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1; } public static void main(String[] args) { // Input 1 int T = 5, A = 1, B = 100; // Function Call System.out.println(countInRange(T, A, B)); // Input 2 int T1 = 5, A1 = 1, B1 = 100000000; // Function Call System.out.println(countInRange(T1, A1, B1)); }}// This code is contributed by lokeshmvs21. |
Python3
MOD = 1e9 + 7# Dp table initialized with -1dp = [[[[-1 for x in range(190)] for y in range(10)] for z in range(21)] for w in range(21)]# Recursive Function to find numbers# in the range A to B such that adjacent# digits are different and their sum is# equal to Tdef recur(i, j, k, sum, T, a): # Base case if i == len(a): # If current sum is equal to T if sum == T: return 1 # If not equal to T else: return 0 # If answer for current state is already # calculated then just # return dp[i][j][k][sum] if dp[i][j][k][sum] != -1: return dp[i][j][k][sum] # Answer initialized with zero ans = 0 # Choosing first value if i == 0: # Iterating from 0 to maxvalue # of digit current position # can have for l in range(int(a[j])+1): # l is maximum value of digit if l == int(a[j]): # Calling recursive function # for selecting last max digit # for current position ans += recur(i+1, j+1, l, sum+l, T, a) else: # Calling recursive function # for selecting l as current # digit and its not max digit ans += recur(i+1, j, l, sum+l, T, a) else: # Digits taken till now were # all zero if sum == 0: # All digits can be possible # from 0 to 9 for l in range(10): # Calling recursive function # for all digits from 0 to 9 ans += recur(i+1, j, l, sum+l, T, a) # Already non zero digits are taken else: # Iterating from 0 to 9 for l in range(10): # If max digit was taken # last time if j == i: # If current digit # is different if l <= int(a[j]) and l != k: # max digit taken calling # recursive function if l == int(a[j]): ans += recur(i+1, j+1, l, sum+l, T, a) # Calling recursive # function for non # max digit else: ans += recur(i+1, j, l, sum+l, T, a) # If max digit was not taken elif l != k: ans += recur(i+1, j, l, sum+l, T, a) # Save and return dp value dp[i][j][k][sum] = ans return ans# Function to find numbers# in the range A to B such that adjacent# digits are different and their sum is# equal to Tdef countInRange(T, A, B): global dp # Initializing dp array with - 1 dp = [[[[-1 for x in range(190)] for y in range(10)] for z in range(21)] for w in range(21)] A -= 1 L = str(A) R = str(B) # Numbers with sum of digits T from # 1 to L - 1 ans1 = recur(0, 0, 0, 0, T, L) # Initializing dp array with - 1 dp = [[[[-1 for x in range(190)] for y in range(10)] for z in range(21)] for w in range(21)] # Numbers with sum of digits T in # the range A to B ans2 = recur(0, 0, 0, 0, T, R) # Return the final answer return (ans2 - ans1 + MOD) % MODif __name__ == '__main__': #Input1 T = 5 A = 1 B = 100 # Function call to find numbers print(int(countInRange(T, A, B))) T = 5 A = 1 B = 100000000 # Function call to find numbers print(int(countInRange(T, A, B))) # This code is contributed by Potta Lokesh |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG{ static int MOD = 1000000007; // Dp table initialized with -1 static int[,,,] dp=new int[21,21,10,190]; // Recursive Function to find numbers // in the range A to B such that adjacent // digits are different and their sum is // equal to T static int recur(int i, int j, int k, int sum, int T, string a) { // Base case if (i == a.Length) { // If current sum is equal to T if (sum == T) return 1; // If not equal to T else return 0; } // If answer for current state is already // calculated then just // return dp[i,j,k,sum] if (dp[i,j,k,sum] != -1) return dp[i,j,k,sum]; // Answer initialized with zero int ans = 0; // Choosing first value if (i == 0) { // Iterating from 0 to maxvalue // of digit current position // can have for (int l = 0; l <= (a[j] - '0'); l++) { // l is maximum value of digit if (l ==(a[j] - '0')) { // Calling recursive function // for selecting last max digit // for current position ans += recur(i + 1, j + 1, l, sum + l, T, a); } else // Calling recursive function // for selecting l as current // digit and its not max digit ans += recur(i + 1, j, l, sum + l, T, a); } } else { // Digits taken till now were // all zero if (sum == 0) { // All digits can be possible // from 0 to 9 for (int l = 0; l <= 9; l++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, j, l, sum + l, T, a); } } // Already non zero digits are taken else { // Iterating from 0 to 9 for (int l = 0; l <= 9; l++) { // If max digit was taken // last time if (j == i) { // If current digit // is different if (l <= (a[j] - '0') && l != k) { // max digit taken calling // recursive function if (l == (a[j] - '0')) ans += recur(i + 1, j + 1, l, sum + l, T, a); // Calling recursive // function for non // max digit else ans += recur(i + 1, j, l, sum + l, T, a); } } // If max digit was not taken else if (l != k) ans += recur(i + 1, j, l, sum + l, T, a); } } } // Save and return dp value return dp[i,j,k,sum] = ans; } // Function to find numbers // in the range A to B such that adjacent // digits are different and their sum is // equal to T static int countInRange(int T, int A, int B) { // Initializing dp array with - 1 for(int i=0; i<21; i++) { for(int j=0; j<21; j++) { for(int k=0; k<10; k++) { for(int l=0; l<190; l++) dp[i,j,k,l]=-1; } } } A--; string L = A.ToString(), R = B.ToString(); // Numbers with sum of digits T from // 1 to L - 1 int ans1 = recur(0, 0, 0, 0, T, L); // Initializing dp array with - 1 for(int i=0; i<21; i++) { for(int j=0; j<21; j++) { for(int k=0; k<10; k++) { for(int l=0; l<190; l++) dp[i,j,k,l]=-1; } } } // Numbers with sum of digits T in // the range 1 to R int ans2 = recur(0, 0, 0, 0, T, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1; } // Driver Code static void Main(string[] args) { // Input 1 int T = 5, A = 1, B = 100; // Function Call Console.WriteLine(countInRange(T, A, B)); // Input 2 int T1 = 5, A1 = 1, B1 = 100000000; // Function Call Console.WriteLine(countInRange(T1, A1, B1)); }} |
Javascript
// Javascript code to implement the approachlet MOD = 1e9 + 7;// Dp table initialized with -1//let dp[21][21][10][190];let dp = new Array(21);function memset(dp, x){ for(let i = 0; i < 21; i++) { dp[i] = new Array(21); for(let j = 0; j < 21; j++) { dp[i][j] = new Array(10); for(let k = 0; k < 10; k++) dp[i][j][k] = new Array(190).fill(-1); } }}// Recursive Function to find numbers// in the range A to B such that adjacent// digits are different and their sum is// equal to Tfunction recur(i, j, k, sum, T, a){ // Base case if (i == a.length) { // If current sum is equal to T if (sum == T) return 1; // If not equal to T else return 0; } // If answer for current state is already // calculated then just // return dp[i][j][k][sum] if (dp[i][j][k][sum] != -1) return dp[i][j][k][sum]; // Answer initialized with zero let ans = 0; // Choosing first value if (i == 0) { // Iterating from 0 to maxvalue // of digit current position // can have for (let l = 0; l <= parseInt(a[j]); l++) { // l is maximum value of digit if (l == parseInt(a[j])) { // Calling recursive function // for selecting last max digit // for current position ans += recur(i + 1, j + 1, l, sum + l, T, a); } else // Calling recursive function // for selecting l as current // digit and its not max digit ans += recur(i + 1, j, l, sum + l, T, a); } } else { // Digits taken till now were // all zero if (sum == 0) { // All digits can be possible // from 0 to 9 for (let l = 0; l <= 9; l++) { // Calling recursive function // for all digits from 0 to 9 ans += recur(i + 1, j, l, sum + l, T, a); } } // Already non zero digits are taken else { // Iterating from 0 to 9 for (let l = 0; l <= 9; l++) { // If max digit was taken // last time if (j == i) { // If current digit // is different if (l <= parseInt(a[j]) && l != k) { // max digit taken calling // recursive function if (l == parseInt(a[j])) ans += recur(i + 1, j + 1, l, sum + l, T, a); // Calling recursive // function for non // max digit else ans += recur(i + 1, j, l, sum + l, T, a); } } // If max digit was not taken else if (l != k) ans += recur(i + 1, j, l, sum + l, T, a); } } } // Save and return dp value return dp[i][j][k][sum] = ans;}// Function to find numbers// in the range A to B such that adjacent// digits are different and their sum is// equal to Tfunction countInRange(T, A, B){ // Initializing dp array with - 1 memset(dp, -1); A--; let L = A.toString(), R = B.toString(); // Numbers with sum of digits T from // 1 to L - 1 let ans1 = recur(0, 0, 0, 0, T, L); // Initializing dp array with - 1 memset(dp, -1); // Numbers with sum of digits T in // the range 1 to R let ans2 = recur(0, 0, 0, 0, T, R); // Difference of ans2 and ans1 // will generate answer for // required range return ans2 - ans1;}// Driver Code // Input 1let T = 5, A = 1, B = 100;// Function Callconsole.log(countInRange(T, A, B));// Input 2let T1 = 5, A1 = 1, B1 = 100000000;// Function Callconsole.log(countInRange(T1, A1, B1));// This code is contributed by ritaagarwal. |
Output
6 74
Time Complexity: O(N2 * M * K2)
Auxiliary Space: O(N2 * M * K)
Related Articles:
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!
