Given the integers N, K and M, the task is to find the Kth number greater than N whose sum of digits is divisible by M.
Examples:
Input: N = 6, K = 5, M = 5
Output: 32
Explanation:
The number greater than N = 6 with the sum of their digits divisible by 5 are {14, 19, 23, 28, 32, …}. The Kth number i.e., the 5th number is 32.Input: N = 40, K = 4, M = 5
Output: 55
Explanation:
The number greater than N = 40 with the sum of their digits divisible by 5 are {41, 46, 50, 55, …}. The Kth number i.e., the 4th number is 55.
Naive Approach: The simplest approach is to check every number greater than N and if the sum of its digits is divisible by M, increment the counter by 1. Keep checking the number until the counter becomes equal to K.
Time Complexity: O(K)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use Dynamic Programming and Binary Search. Follow the below steps to solve the problem:
- First, create a recursive memorized function to find the total number of integers smaller than or equal to S having the sum of digits divisible by M as shown below:
The dp transitions will be:
dp(S, index, sum, tight, M) = dp(index+1, (sum+i)%M, tight, M) where,
- S is given limit for which all numbers smaller than or equal to S with the sum of digits divisible by M needs to be found.
- index is the current index for which a digit needs to be placed.
- sum takes the values from 0 to 4.
- Base condition is, if index becomes greater than the length of S and sum is divisible by M, return 1.
- M is the divisor.
If the previous digit already placed such that it becomes smaller than S then
- tight will become equal to 0.
- i will iterate from 0 to 9.
If all the previous digits match with the corresponding digits in S, then
- tight will become 1, which denotes that the number is still not become smaller than S.
- i will iterate from 0 to digit S[index].
- Now using Binary Search, where the lower limit will be N+1 and the upper limit will be some large integer.
- Initialize a variable left for storing the total numbers smaller than or equal to N whose sum of digits is divisible by M.
- Find the midpoint of the lower and the upper limit and then find the numbers smaller than or equal midpoint whose sum of digits is divisible by M using the above dp function. Let it be right.
- If left + K is equals to right then, update the answer as mid and set the upper limit as midpoint – 1.
- Otherwise, if left + K is smaller than right, set the upper limit as midpoint-1.
- If left + K is greater than right, set the lower limit as midpoint+1.
- Repeat the above steps, while the lower limit is smaller than or equal to the upper limit.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Initialize dp arrayint dp[100000][100][2];// Function to find the numbers <= S// having digits sum divisible by Mint solve(string s, int index, int sum, int tight, int z){ // Base Case if (index >= s.size()) { if (sum % z == 0) return 1; return 0; } // Visited state if (dp[index][sum][tight] != -1) return dp[index][sum][tight]; // Store answer int ans = 0; // If number still does not // become smaller than S if (tight == 1) { // Find limit int l = s[index] - '0'; // Iterate through all // the digits for(int i = 0; i <= l; i++) { // If current digit is limit if (i == l) { ans += solve(s, index + 1, (sum + i) % z, 1, z); } // Number becomes smaller than S else { ans += solve(s, index + 1, (sum + i) % z, 0, z); } } } else { // If number already becomes // smaller than S for(int i = 0; i <= 9; i++) ans += solve(s, index + 1, (sum + i) % z, 0, z); } // Return and store the answer // for the current state return dp[index][sum][tight] = ans;}// Function to find the Kth number// > N whose sum of the digits is// divisible by Mint search(int n, int k, int z){ // Initialize lower limit int low = n + 1; // Initialize upper limit int high = 1e9; // Mask dp states unvisited memset(dp, -1, sizeof(dp)); // Numbers <= N except 0 with // digits sum divisible by M int left = solve(to_string(n), 0, 0, 1, z) - 1; // Initialize answer with -1 int ans = -1; while (low <= high) { // Calculate mid int mid = low + (high - low) / 2; // Mark dp states unvisited memset(dp, -1, sizeof(dp)); // Numbers < mid with digits // sum divisible by M int right = solve(to_string(mid), 0, 0, 1, z) - 1; // If the current mid is // satisfy the condition if (left + k == right) { // Might be the answer ans = mid; // Update upper limit high = mid - 1; } else if (left + k < right) { // Update upper limit high = mid - 1; } else { // Update lower limit low = mid + 1; } } // Return the answer return ans;}// Driver Codeint main(){ // Given N, K, and M int N = 40; int K = 4; int M = 2; // Function Call cout << search(N, K, M) << endl;}// This code is contributed by bolliranadheer |
Java
// Java program for the above approachimport java.util.*;public class Main { static int dp[][][]; // Function to find the Kth number // > N whose sum of the digits is // divisible by M public static int search( int n, int k, int z) { // Initialize dp array dp = new int[100000 + 1][z][2]; // Initialize lower limit int low = n + 1; // Initialize upper limit int high = Integer.MAX_VALUE / 2; // Mask dp states unvisited clear(); // Numbers <= N except 0 with // digits sum divisible by M int left = solve(n + "", 0, 0, 1, z) - 1; // Initialize answer with -1 int ans = -1; while (low <= high) { // Calculate mid int mid = low + (high - low) / 2; // Mark dp states unvisited clear(); // Numbers < mid with digits // sum divisible by M int right = solve(mid + "", 0, 0, 1, z) - 1; // If the current mid is // satisfy the condition if (left + k == right) { // Might be the answer ans = mid; // Update upper limit high = mid - 1; } else if (left + k < right) { // Update upper limit high = mid - 1; } else { // Update lower limit low = mid + 1; } } // Return the answer return ans; } // Function to find the numbers <= S // having digits sum divisible by M public static int solve( String s, int index, int sum, int tight, int z) { // Base Case if (index >= s.length()) { if (sum % z == 0) return 1; return 0; } // Visited state if (dp[index][sum][tight] != -1) return dp[index][sum][tight]; // Store answer int ans = 0; // If number still does not // become smaller than S if (tight == 1) { // Find limit int l = s.charAt(index) - '0'; // Iterate through all // the digits for (int i = 0; i <= l; i++) { // If current digit is limit if (i == l) { ans += solve(s, index + 1, (sum + i) % z, 1, z); } // Number becomes smaller than S else { ans += solve(s, index + 1, (sum + i) % z, 0, z); } } } else { // If number already becomes // smaller than S for (int i = 0; i <= 9; i++) ans += solve(s, index + 1, (sum + i) % z, 0, z); } // Return and store the answer // for the current state return dp[index][sum][tight] = ans; } // Function to clear the states public static void clear() { for (int i[][] : dp) { for (int j[] : i) Arrays.fill(j, -1); } } // Driver Code public static void main(String args[]) { // Given N, K, and M int N = 40; int K = 4; int M = 2; // Function Call System.out.println(search(N, K, M)); }} |
Python3
# Python program for the# above approach# Initialize dp arraydp = [[[]]]# Function to find the # numbers <= S having # digits sum divisible # by Mdef solve(s, index, sum,tight, z): # Base Case if (index >= len(s)): if (sum % z == 0): return 1 return 0 # Visited state if (dp[index][sum][tight] != -1): return dp[index][sum][tight] # Store answer ans = 0 # If number still does not # become smaller than S if(tight == 1): # Find limit l = int(ord(s[index]) - ord('0')) # Iterate through all # the digits for i in range(0, l + 1): # If current digit is # limit if (i == l): ans += solve(s, index + 1, (sum + i) % z, 1, z) # Number becomes smaller # than S else: ans += solve(s, index + 1, (sum + i) % z, 0, z) else: # If number already becomes # smaller than S for i in range(0,10): ans += solve(s, index + 1, (sum + i) % z, 0, z) # Return and store the answer # for the current state dp[index][sum][tight] = ans return ans# Function to find the Kth number# > N whose sum of the digits is# divisible by Mdef search(n, k, z): global dp dp = [[[-1, -1] for j in range(z)] for i in range(100001)] # Initialize lower limit low = n + 1 # Initialize upper limit high = 1000000009 # Numbers <= N except 0 with # digits sum divisible by M left = solve(str(n), 0, 0, 1, z) - 1 # Initialize answer with -1 ans = -1 while (low <= high): # Calculate mid mid = low + (high - low) // 2 # Mark dp states unvisited dp = [[[-1, -1] for j in range(z)] for i in range(100000)] # Numbers < mid with digits # sum divisible by M right = solve(str(mid), 0, 0, 1, z) - 1 # If the current mid is # satisfy the condition if (left + k == right): # Might be the answer ans = mid # Update upper limit high = mid - 1 elif (left + k < right): # Update upper limit high = mid - 1 else: # Update lower limit low = mid + 1 # Return the answer return ans# Driver Codeif __name__ == "__main__": # Given N, K, and M N = 40 K = 4 M = 2 # Function Call print(search(N, K, M))# This code is contributed by Rutvik_56 |
C#
// C# program for the above approachusing System;class GFG{static int [,,]dp;// Function to find the Kth number// > N whose sum of the digits is// divisible by Mpublic static int search(int n, int k, int z){ // Initialize dp array dp = new int[100000 + 1, z, 2]; // Initialize lower limit int low = n + 1; // Initialize upper limit int high = int.MaxValue / 2; // Mask dp states unvisited Clear(z); // Numbers <= N except 0 with // digits sum divisible by M int left = solve(n + "", 0, 0, 1, z) - 1; // Initialize answer with -1 int ans = -1; while (low <= high) { // Calculate mid int mid = low + (high - low) / 2; // Mark dp states unvisited Clear(z); // Numbers < mid with digits // sum divisible by M int right = solve(mid + "", 0, 0, 1, z) - 1; // If the current mid is // satisfy the condition if (left + k == right) { // Might be the answer ans = mid; // Update upper limit high = mid - 1; } else if (left + k < right) { // Update upper limit high = mid - 1; } else { // Update lower limit low = mid + 1; } } // Return the answer return ans;}// Function to find the numbers <= S// having digits sum divisible by Mpublic static int solve(String s, int index, int sum, int tight, int z){ // Base Case if (index >= s.Length) { if (sum % z == 0) return 1; return 0; } // Visited state if (dp[index, sum, tight] != -1) return dp[index, sum, tight]; // Store answer int ans = 0; // If number still does not // become smaller than S if (tight == 1) { // Find limit int l = s[index] - '0'; // Iterate through all // the digits for(int i = 0; i <= l; i++) { // If current digit is limit if (i == l) { ans += solve(s, index + 1, (sum + i) % z, 1, z); } // Number becomes smaller than S else { ans += solve(s, index + 1, (sum + i) % z, 0, z); } } } else { // If number already becomes // smaller than S for(int i = 0; i <= 9; i++) ans += solve(s, index + 1, (sum + i) % z, 0, z); } // Return and store the answer // for the current state return dp[index, sum, tight] = ans;}// Function to clear the statespublic static void Clear(int z){ for(int i = 0; i < 100001; i++) { for(int j = 0; j < z; j++) { for(int l = 0; l < 2; l++) dp[i, j, l] = -1; } }}// Driver Codepublic static void Main(String []args){ // Given N, K, and M int N = 40; int K = 4; int M = 2; // Function Call Console.WriteLine(search(N, K, M));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approachlet dp;// Function to find the Kth number // > N whose sum of the digits is // divisible by Mfunction search(n,k,z){ // Initialize dp array dp = new Array(100000 + 1); for(let i=0;i<100000+1;i++) { dp[i]=new Array(z); for(let j=0;j<z;j++) { dp[i][j]=new Array(2); } } // Initialize lower limit let low = n + 1; // Initialize upper limit let high = Math.floor(Number.MAX_VALUE / 2); // Mask dp states unvisited clear(); // Numbers <= N except 0 with // digits sum divisible by M let left = solve(n + "", 0, 0, 1, z) - 1; // Initialize answer with -1 let ans = -1; while (low <= high) { // Calculate mid let mid = low + Math.floor((high - low) / 2); // Mark dp states unvisited clear(); // Numbers < mid with digits // sum divisible by M let right = solve(mid + "", 0, 0, 1, z) - 1; // If the current mid is // satisfy the condition if (left + k == right) { // Might be the answer ans = mid; // Update upper limit high = mid - 1; } else if (left + k < right) { // Update upper limit high = mid - 1; } else { // Update lower limit low = mid + 1; } } // Return the answer return ans;}// Function to find the numbers <= S // having digits sum divisible by Mfunction solve(s,index,sum,tight,z){ // Base Case if (index >= s.length) { if (sum % z == 0) return 1; return 0; } // Visited state if (dp[index][sum][tight] != -1) return dp[index][sum][tight]; // Store answer let ans = 0; // If number still does not // become smaller than S if (tight == 1) { // Find limit let l = s[index].charCodeAt(0) - '0'.charCodeAt(0); // Iterate through all // the digits for (let i = 0; i <= l; i++) { // If current digit is limit if (i == l) { ans += solve(s, index + 1, (sum + i) % z, 1, z); } // Number becomes smaller than S else { ans += solve(s, index + 1, (sum + i) % z, 0, z); } } } else { // If number already becomes // smaller than S for (let i = 0; i <= 9; i++) ans += solve(s, index + 1, (sum + i) % z, 0, z); } // Return and store the answer // for the current state return dp[index][sum][tight] = ans;}// Function to clear the statesfunction clear(){ for(let i=0;i<dp.length;i++) { for(let j=0;j<dp[i].length;j++) { for(let k=0;k<dp[i][j].length;k++) { dp[i][j][k]=-1; } } }}// Driver Code// Given N, K, and Mlet N = 40;let K = 4;let M = 2;// Function Calldocument.write(search(N, K, M)+"<br>");// This code is contributed by patel2127</script> |
Output
48
Time Complexity: O(log(INT_MAX))
Auxiliary Space: O(K * M * log(INT_MAX))
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!
