Given integers A, B, and N, the task is to find the total number of N-digit numbers whose sum of digits at even positions and odd positions are divisible by A and B respectively.
Examples:
Input: N = 2, A = 2, B = 5
Output: 5
Explanation:
The only 2-digit numbers {50, 52, 54, 56, 58} with sum of odd-positioned digits equal to 5 and even-positioned digits {0, 2, 4, 6, 8} divisible by 2.Input: N = 2, A = 5, B = 3
Output: 6
Explanation:
The only two-digit numbers {30, 35, 60, 65, 90, 95} have odd digits {3, 6 or 9}, which is divisible by 3 and even digits {0 or 5}, which is divisible by 5.
Naive Approach: The simplest approach to solve this problem is to iterate over all possible N-digit numbers and for each number, check if the sum of digits at even positions is divisible by A and the sum of digits at odd positions is divisible by B or not. If found to be true, increase count.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate and// return the reverse of the numberlong reverse(long num){ long rev = 0; while (num > 0) { int r = (int)(num % 10); rev = rev * 10 + r; num /= 10; } return rev;}// Function to calculate the total// count of N-digit numbers satisfying// the necessary conditionslong count(int N, int A, int B){ // Initialize two variables long l = (long)pow(10, N - 1), r = (long)pow(10, N) - 1; if (l == 1) l = 0; long ans = 0; for(long i = l; i <= r; i++) { int even_sum = 0, odd_sum = 0; long itr = 0, num = reverse(i); // Calculate the sum of odd // and even positions while (num > 0) { if (itr % 2 == 0) odd_sum += num % 10; else even_sum += num % 10; num /= 10; itr++; } // Check for divisibility if (even_sum % A == 0 && odd_sum % B == 0) ans++; } // Return the answer return ans;}// Driver Codeint main(){ int N = 2, A = 5, B = 3; cout << (count(N, A, B));}// This code is contributed by 29AjayKumar |
Java
// Java Program to implement// the above approachclass GFG { // Function to calculate and // return the reverse of the number public static long reverse(long num) { long rev = 0; while (num > 0) { int r = (int)(num % 10); rev = rev * 10 + r; num /= 10; } return rev; } // Function to calculate the total // count of N-digit numbers satisfying // the necessary conditions public static long count(int N, int A, int B) { // Initialize two variables long l = (long)Math.pow(10, N - 1), r = (long)Math.pow(10, N) - 1; if (l == 1) l = 0; long ans = 0; for (long i = l; i <= r; i++) { int even_sum = 0, odd_sum = 0; long itr = 0, num = reverse(i); // Calculate the sum of odd // and even positions while (num > 0) { if (itr % 2 == 0) odd_sum += num % 10; else even_sum += num % 10; num /= 10; itr++; } // Check for divisibility if (even_sum % A == 0 && odd_sum % B == 0) ans++; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { int N = 2, A = 5, B = 3; System.out.println(count(N, A, B)); }} |
Python3
# Python3 Program to implement# the above approach# Function to calculate and# return the reverse of the numberdef reverse(num): rev = 0; while (num > 0): r = int(num % 10); rev = rev * 10 + r; num = num // 10; return rev;# Function to calculate the total# count of N-digit numbers satisfying# the necessary conditionsdef count(N, A, B): # Initialize two variables l = int(pow(10, N - 1)); r = int(pow(10, N) - 1); if (l == 1): l = 0; ans = 0; for i in range(l, r + 1): even_sum = 0; odd_sum = 0; itr = 0; num = reverse(i); # Calculate the sum of odd # and even positions while (num > 0): if (itr % 2 == 0): odd_sum += num % 10; else: even_sum += num % 10; num = num // 10; itr += 1; # Check for divisibility if (even_sum % A == 0 and odd_sum % B == 0): ans += 1; # Return the answer return ans;# Driver Codeif __name__ == '__main__': N = 2; A = 5; B = 3; print(count(N, A, B));# This code is contributed by gauravrajput1 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to calculate and// return the reverse of the numberpublic static long reverse(long num){ long rev = 0; while (num > 0) { int r = (int)(num % 10); rev = rev * 10 + r; num /= 10; } return rev;}// Function to calculate the total// count of N-digit numbers satisfying// the necessary conditionspublic static long count(int N, int A, int B){ // Initialize two variables long l = (long)Math.Pow(10, N - 1), r = (long)Math.Pow(10, N) - 1; if (l == 1) l = 0; long ans = 0; for(long i = l; i <= r; i++) { int even_sum = 0, odd_sum = 0; long itr = 0, num = reverse(i); // Calculate the sum of odd // and even positions while (num > 0) { if (itr % 2 == 0) odd_sum += (int)num % 10; else even_sum += (int)num % 10; num /= 10; itr++; } // Check for divisibility if (even_sum % A == 0 && odd_sum % B == 0) ans++; } // Return the answer return ans;}// Driver Codepublic static void Main(String[] args){ int N = 2, A = 5, B = 3; Console.WriteLine(count(N, A, B));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript Program to implement// the above approach // Function to calculate and // return the reverse of the number function reverse(num) { var rev = 0; while (num > 0) { var r = parseInt( (num % 10)); rev = rev * 10 + r; num = parseInt(num/10); } return rev; } // Function to calculate the total // count of N-digit numbers satisfying // the necessary conditions function count(N , A , B) { // Initialize two variables var l = Math.pow(10, N - 1), r = Math.pow(10, N) - 1; if (l == 1) l = 0; var ans = 0; for (i = l; i <= r; i++) { var even_sum = 0, odd_sum = 0; var itr = 0, num = reverse(i); // Calculate the sum of odd // and even positions while (num > 0) { if (itr % 2 == 0) odd_sum += num % 10; else even_sum += num % 10; num = parseInt(num/10); itr++; } // Check for divisibility if (even_sum % A == 0 && odd_sum % B == 0) ans++; } // Return the answer return ans; } // Driver Code var N = 2, A = 5, B = 3; document.write(count(N, A, B));// This code contributed by aashish1995 </script> |
Output:
6
Time Complexity: O((10N – 10N – 1 – 1) * N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, use the concept of Dynamic Programming.
Follow the steps below to solve the problem:
- Since the even-positioned digits and the odd-positioned digits are not dependent on each other, therefore, the given problem can be broken down into two subproblems:
- For even-positioned digits: Total count of sequences of N/2 digits from 0 to 9 (repetitions allowed) such that the sum of digits is divisible by A, where the first digit can be zero.
- For odd-positioned digits: Total count of sequences of Ceil(N/2) digits from 0 to 9 (repetitions allowed) such that the sum of digits is divisible by B, where the first digit cannot be zero.
- The required result is the product of the above two.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the total// count of N-digit numbers such// that the sum of digits at even// positions and odd positions are// divisible by A and B respectivelylong count(int N, int A, int B){ // For single digit numbers if (N == 1) { return 9 / B + 1; } // Largest possible number int max_sum = 9 * N; // Count of possible odd digits int odd_count = N / 2 + N % 2; // Count of possible even digits int even_count = N - odd_count; // Calculate total count of sequences of // length even_count with sum divisible // by A where first digit can be zero long dp[even_count][max_sum + 1] = {0}; for (int i = 0; i <= 9; i++) dp[0][i % A]++; for (int i = 1; i < even_count; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= max_sum; k++) { if (dp[i - 1][k] > 0) dp[i][(j + k) % A] += dp[i - 1][k]; } } } // Calculate total count of sequences of // length odd_count with sum divisible // by B where cannot be zero long dp1[odd_count][max_sum + 1] = {0}; for (int i = 1; i <= 9; i++) dp1[0][i % B]++; for (int i = 1; i < odd_count; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= max_sum; k++) { if (dp1[i - 1][k] > 0) dp1[i][(j + k) % B] += dp1[i - 1][k]; } } } // Return their product as answer return dp[even_count - 1][0] * dp1[odd_count - 1][0];}// Driver Codeint main(){ int N = 2, A = 2, B = 5; cout << count(N, A, B);}// This code is contributed by Rajput-Ji |
Java
// Java Program to implement// the above approachclass GFG { // Function to calculate the total // count of N-digit numbers such // that the sum of digits at even // positions and odd positions are // divisible by A and B respectively public static long count(int N, int A, int B) { // For single digit numbers if (N == 1) { return 9 / B + 1; } // Largest possible number int max_sum = 9 * N; // Count of possible odd digits int odd_count = N / 2 + N % 2; // Count of possible even digits int even_count = N - odd_count; // Calculate total count of sequences of // length even_count with sum divisible // by A where first digit can be zero long dp[][] = new long[even_count][max_sum + 1]; for (int i = 0; i <= 9; i++) dp[0][i % A]++; for (int i = 1; i < even_count; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= max_sum; k++) { if (dp[i - 1][k] > 0) dp[i][(j + k) % A] += dp[i - 1][k]; } } } // Calculate total count of sequences of // length odd_count with sum divisible // by B where cannot be zero long dp1[][] = new long[odd_count][max_sum + 1]; for (int i = 1; i <= 9; i++) dp1[0][i % B]++; for (int i = 1; i < odd_count; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= max_sum; k++) { if (dp1[i - 1][k] > 0) dp1[i][(j + k) % B] += dp1[i - 1][k]; } } } // Return their product as answer return dp[even_count - 1][0] * dp1[odd_count - 1][0]; } // Driver Code public static void main(String[] args) { int N = 2, A = 2, B = 5; System.out.println(count(N, A, B)); }} |
Python3
# Python 3 Program to implement# the above approach# Function to calculate the total# count of N-digit numbers such# that the sum of digits at even# positions and odd positions are# divisible by A and B respectivelydef count(N, A, B): # For single digit numbers if (N == 1): return 9 // B + 1 # Largest possible number max_sum = 9 * N # Count of possible odd digits odd_count = N // 2 + N % 2 # Count of possible even digits even_count = N - odd_count # Calculate total count of # sequences of length even_count # with sum divisible by A where # first digit can be zero dp = [[0 for x in range (max_sum + 1)] for y in range (even_count)] for i in range(10): dp[0][i % A] += 1 for i in range (1, even_count): for j in range (10): for k in range (max_sum + 1): if (dp[i - 1][k] > 0): dp[i][(j + k) % A] += dp[i - 1][k] # Calculate total count of sequences of # length odd_count with sum divisible # by B where cannot be zero dp1 = [[0 for x in range (max_sum)] for y in range (odd_count)] for i in range (1, 10): dp1[0][i % B] += 1 for i in range (1, odd_count): for j in range (10): for k in range (max_sum + 1): if (dp1[i - 1][k] > 0): dp1[i][(j + k) % B] += dp1[i - 1][k] # Return their product as answer return dp[even_count - 1][0] * dp1[odd_count - 1][0]# Driver Codeif __name__ == "__main__": N = 2 A = 2 B = 5 print (count(N, A, B))# This code is contributed by Chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to calculate the total// count of N-digit numbers such// that the sum of digits at even// positions and odd positions are// divisible by A and B respectivelypublic static long count(int N, int A, int B){ // For single digit numbers if (N == 1) { return 9 / B + 1; } // Largest possible number int max_sum = 9 * N; // Count of possible odd digits int odd_count = N / 2 + N % 2; // Count of possible even digits int even_count = N - odd_count; // Calculate total count of sequences of // length even_count with sum divisible // by A where first digit can be zero long [,]dp = new long[even_count, max_sum + 1]; for(int i = 0; i <= 9; i++) dp[0, i % A]++; for(int i = 1; i < even_count; i++) { for(int j = 0; j <= 9; j++) { for(int k = 0; k <= max_sum; k++) { if (dp[i - 1, k] > 0) dp[i, (j + k) % A] += dp[i - 1, k]; } } } // Calculate total count of sequences of // length odd_count with sum divisible // by B where cannot be zero long [,]dp1 = new long[odd_count, max_sum + 1]; for(int i = 1; i <= 9; i++) dp1[0, i % B]++; for(int i = 1; i < odd_count; i++) { for(int j = 0; j <= 9; j++) { for(int k = 0; k <= max_sum; k++) { if (dp1[i - 1, k] > 0) dp1[i, (j + k) % B] += dp1[i - 1, k]; } } } // Return their product as answer return dp[even_count - 1, 0] * dp1[odd_count - 1, 0];}// Driver Codepublic static void Main(String[] args){ int N = 2, A = 2, B = 5; Console.WriteLine(count(N, A, B));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach // Function to calculate the total // count of N-digit numbers such // that the sum of digits at even // positions and odd positions are // divisible by A and B respectively function count(N, A, B) { // For single digit numbers if (N == 1) { return 9 / B + 1; } // Largest possible number let max_sum = 9 * N; // Count of possible odd digits let odd_count = N / 2 + N % 2; // Count of possible even digits let even_count = N - odd_count; // Calculate total count of sequences of // length even_count with sum divisible // by A where first digit can be zero let dp = new Array(even_count); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for (var i = 0; i < even_count; i++) { for (var j = 0; j < max_sum + 1; j++) { dp[i][j] = 0; } } for (let i = 0; i <= 9; i++) dp[0][i % A]++; for (let i = 1; i < even_count; i++) { for (let j = 0; j <= 9; j++) { for (let k = 0; k <= max_sum; k++) { if (dp[i - 1][k] > 0) dp[i][(j + k) % A] += dp[i - 1][k]; } } } // Calculate total count of sequences of // length odd_count with sum divisible // by B where cannot be zero let dp1 = new Array(odd_count); // Loop to create 2D array using 1D array for (var i = 0; i < dp1.length; i++) { dp1[i] = new Array(2); } for (var i = 0; i < odd_count; i++) { for (var j = 0; j < max_sum + 1; j++) { dp1[i][j] = 0; } } for (let i = 1; i <= 9; i++) dp1[0][i % B]++; for (let i = 1; i < odd_count; i++) { for (let j = 0; j <= 9; j++) { for (let k = 0; k <= max_sum; k++) { if (dp1[i - 1][k] > 0) dp1[i][(j + k) % B] += dp1[i - 1][k]; } } } // Return their product as answer return dp[even_count - 1][0] * dp1[odd_count - 1][0]; } // Driver Code let N = 2, A = 2, B = 5; document.write(count(N, A, B)); </script> |
Output:
5
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
