Given two integers N and X, the task is to find the count of all possible N digit numbers whose every single digit is a multiple of X.
Examples :
Input: N = 1, X = 3
Output: 4
Explanation:
The single-digit numbers whose digits are multiple of 3 are 0, 3, 6 and 9.
So the answer will be 4.
Input: N = 2, X = 4
Output: 6
Explanation:
The two-digit numbers whose digits are multiple of 4 are 40, 44, 48, 80, 84, 88.
So the answer will be 6.
Naive Approach: The simplest approach is to iterate over all N-digit numbers, i.e. in the range [10N – 1, 10N – 1] and for each number, check if each digit of the number is a multiple of X or not. Increase the count of such numbers and print the final count.
Time Complexity: O((10N – 10N – 1)*N)
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below in order to solve the problem:
- Count the total digits which are multiple of X, lets denote it as total_Multiples.
- BY arrange all the above digits in different positions to form an N-digit number the required count can be obtained.
Illustration:
For example N = 2, X = 3
Multiples of 3 are S = { 0, 3, 6, 9 }
- To find all 2-digit numbers, arrange all the multiples of X to form a 2-digit number and count it.
- Arrange the numbers from the set S. Taking 0 for the most significant bit will result in 1-digit number, so there are 3 ways to arrange the most significant position of a number and there are 4 ways to arrange the last digit of a number whose digits are multiples of 3.
So total ways = 3*4 = 12 so the answer will be 12.
- From the above illustration, if M is the count of all multiples of X, then the required count of N digit numbers(for N > 1) is equal to (M – 1)*MN – 1.
- For one-digit numbers, the answer is M.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <stdio.h>#define ll long long// Function to calculate x^n// using binary-exponentiationll power(ll x, ll n){ // Stores the resultant power ll temp; if (n == 0) return 1; // Stores the value of x^(n/2) temp = power(x, n / 2); if (n % 2 == 0) return temp * temp; else return x * temp * temp;}// Function to count all N-digit numbers// whose digits are multiples of xll count_Total_Numbers(ll n, ll x){ ll total, multiples = 0; // Count all digits which // are multiples of x for (int i = 0; i < 10; i++) { // Check if current number // is a multiple of X if (i % x == 0) // Increase count of multiples multiples++; } // Check if it's a 1 digit number if (n == 1) return multiples; // Count the total numbers total = (multiples - 1) * power(multiples, n - 1); // Return the total numbers return total;}// Driver Codeint main(){ // Given N and X ll N = 1, X = 3; // Function Call printf("%lld ", count_Total_Numbers(N, X)); return 0;} |
Java
// Java program for // the above approachclass GFG{// Function to calculate x^n// using binary-exponentiationstatic int power(int x, int n){ // Stores the resultant power int temp; if (n == 0) return 1; // Stores the value of x^(n/2) temp = power(x, n / 2); if (n % 2 == 0) return temp * temp; else return x * temp * temp;}// Function to count all N-digit // numbers whose digits are multiples // of xstatic int count_Total_Numbers(int n, int x){ int total, multiples = 0; // Count all digits which // are multiples of x for (int i = 0; i < 10; i++) { // Check if current number // is a multiple of X if (i % x == 0) // Increase count of multiples multiples++; } // Check if it's a 1 digit number if (n == 1) return multiples; // Count the total numbers total = (multiples - 1) * power(multiples, n - 1); // Return the total numbers return total;}// Driver Codepublic static void main(String[] args){ // Given N and X int N = 1, X = 3; // Function Call System.out.printf("%d ", count_Total_Numbers(N, X));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to calculate x^n# using binary-exponentiationdef power(x, n): # Stores the resultant power temp = [] if (n == 0): return 1 # Stores the value of x^(n/2) temp = power(x, n // 2) if (n % 2 == 0): return temp * temp else: return x * temp * temp# Function to count aN-digit numbers# whose digits are multiples of xdef count_Total_Numbers(n, x): total, multiples = 0, 0 # Count adigits which # are multiples of x for i in range(10): # Check if current number # is a multiple of X if (i % x == 0): # Increase count of multiples multiples += 1 # Check if it's a 1 digit number if (n == 1): return multiples # Count the total numbers total = ((multiples - 1) * power(multiples, n - 1)) # Return the total numbers return total# Driver Codeif __name__ == '__main__': # Given N and X N = 1 X = 3 # Function call print(count_Total_Numbers(N, X))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System;class GFG{// Function to calculate x^n// using binary-exponentiationstatic int power(int x, int n){ // Stores the resultant power int temp; if (n == 0) return 1; // Stores the value of x^(n/2) temp = power(x, n / 2); if (n % 2 == 0) return temp * temp; else return x * temp * temp;}// Function to count all N-digit // numbers whose digits are multiples // of xstatic int count_Total_Numbers(int n, int x){ int total, multiples = 0; // Count all digits which // are multiples of x for(int i = 0; i < 10; i++) { // Check if current number // is a multiple of X if (i % x == 0) // Increase count of multiples multiples++; } // Check if it's a 1 digit number if (n == 1) return multiples; // Count the total numbers total = (multiples - 1) * power(multiples, n - 1); // Return the total numbers return total;}// Driver Codepublic static void Main(){ // Given N and X int N = 1, X = 3; // Function call Console.Write(count_Total_Numbers(N, X));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach// Function to calculate x^n// using binary-exponentiationfunction power(x, n){ // Stores the resultant power let temp; if (n == 0) return 1; // Stores the value of x^(n/2) temp = power(x, parseInt(n / 2)); if (n % 2 == 0) return temp * temp; else return x * temp * temp;}// Function to count all N-digit numbers// whose digits are multiples of xfunction count_Total_Numbers(n, x){ let total, multiples = 0; // Count all digits which // are multiples of x for (let i = 0; i < 10; i++) { // Check if current number // is a multiple of X if (i % x == 0) // Increase count of multiples multiples++; } // Check if it's a 1 digit number if (n == 1) return multiples; // Count the total numbers total = (multiples - 1) * power(multiples, n - 1); // Return the total numbers return total;}// Driver Code // Given N and X let N = 1, X = 3; // Function Call document.write( count_Total_Numbers(N, X));// This code is contributed by subhammahato348.</script> |
Output:
4
Time Complexity: O(Log N)
Auxiliary Space: O(1)
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!
