Given a, b and N(1 to 106). Task is to count the numbers formed by digits a and b exactly of a length N such that the sum of the digits of the number thus formed also contains digits a and b only. Since the count can be very large, print the count % 1000000007.
Examples :
Input : a = 1 b = 3 n = 3 Output : 1 Explanation : The only number is 111 of length 3, the sum of digits of 111 is 3, which is b. Input : a = 6 b = 9 n = 1 Output : 2 Explanation : The numbers of length 1 is 6 and 9, whose sum of digits is 6 and 9 respectively which is a and b respectively. Input: a = 2 b = 3 n = 10 Output : 165
Approach:
Since N is very large, we cannot iterate for all numbers to check them individually. As the number is of length N and formed by two digits a and b, a will occupy i positions and b will occupy n – i positions. The sum of digits thus will be ( a*i + (n-i)*b ).
We can check if the sum of digits is formed of a and b for all i ranging from 0 to N. Thus, the total count of numbers formed will be 
which will correspond to all combination of numbers formed by a and b whose sum of digits is also formed of a and b.
Implement Modular Operations in calculations :
Calculate %1000000007 for all i ranging from 0 to N satisfying the given condition.
A simple solution will give answer as :
(factorial(n) * modInverse(n - i) * modInverse(i)) % mod
Since calculating the modInverse takes O(log N), the total time complexity will be O(N log N), if all the factorials are pre-calculated.
An efficient solution will be to precalculate all the factorials till N. Calculate the modInverse of N! in O(log N) and calculate the modInverse of all factorials from (N – 1)! to 1! by the given below formula.
modInverse(i!) = modInverse((i + 1)!) * (i + 1)
Below is the implementation of the above approach :
C++
// C++ program to count the number// of numbers formed by digits a// and b exactly of a length N such// that the sum of the digits of the// number thus formed is of digits a and b.#include <bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;const int N = 1000005;int fact[N], invfact[N];// function to check if sum of// digits is made of a and bint check(int x, int a, int b){ // sum of digits is 0 if (x == 0) return 0; while (x) { // if any of digits in sum is // other than a and b if (x % 10 != a and x % 10 != b) return 0; x /= 10; } return 1;}// calculate the modInverse V / of a number in O(log n)int modInverse(int a, int m){ int m0 = m; int y = 0, x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process // same as Euclid's algo m = a % m, a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x;}// function to pregenerate factorialsvoid pregenFact(){ fact[0] = fact[1] = 1; for (int i = 1; i <= 1000000; ++i) fact[i] = (long long)fact[i - 1] * i % mod;}// function to pre calculate the// modInverse of factorialsvoid pregenInverse(){ invfact[0] = invfact[1] = 1; // calculates the modInverse of the last factorial invfact[1000000] = modInverse(fact[1000000], mod); // precalculates the modInverse of all factorials // by formulae for (int i = 999999; i > 1; --i) invfact[i] = ((long long)invfact[i + 1] * (long long)(i + 1)) % mod;}// function that returns the value of nCiint comb(int big, int small){ return (long long)fact[big] * invfact[small] % mod * invfact[big - small] % mod;}// function that returns the count of numbersint count(int a, int b, int n){ // function call to pre-calculate the // factorials and modInverse of factorials pregenFact(); pregenInverse(); // if a and b are same if (a == b) return (check(a * n, a, b)); int ans = 0; for (int i = 0; i <= n; ++i) if (check(i * a + (n - i) * b, a, b)) ans = (ans + comb(n, i)) % mod; return ans;}// Driver Codeint main(){ int a = 3, b = 4, n = 11028; cout << count(a, b, n); return 0;} |
Java
// Java program to count the number// of numbers formed by digits a// and b exactly of a length N such// that the sum of the digits of the// number thus formed is of digits a and b.class GFG { static int mod = (int) (1e9 + 7); static int N = 1000005; static int fact[] = new int[N], invfact[] = new int[N]; // function to check if sum of // digits is made of a and b static int check(int x, int a, int b) { // sum of digits is 0 if (x == 0) { return 0; } while (x > 0) { // if any of digits in sum is // other than a and b if (x % 10 != a & x % 10 != b) { return 0; } x /= 10; } return 1; } // calculate the modInverse V / of a number in O(log n) static int modInverse(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) { return 0; } while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process // same as Euclid's algo m = a % m; a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) { x += m0; } return x; } // function to pregenerate factorials static void pregenFact() { fact[0] = fact[1] = 1; for (int i = 1; i <= 1000000; ++i) { fact[i] = (int) ((long) fact[i - 1] * i % mod); } } // function to pre calculate the // modInverse of factorials static void pregenInverse() { invfact[0] = invfact[1] = 1; // calculates the modInverse of // the last factorial invfact[1000000] = modInverse(fact[1000000], mod); // precalculates the modInverse of // all factorials by formulae for (int i = 999999; i > 1; --i) { invfact[i] = (int) (((long) invfact[i + 1] * (long) (i + 1)) % mod); } } // function that returns the value of nCi static int comb(int big, int small) { return (int) ((long) fact[big] * invfact[small] % mod * invfact[big - small] % mod); } // function that returns the count of numbers static int count(int a, int b, int n) { // function call to pre-calculate the // factorials and modInverse of factorials pregenFact(); pregenInverse(); // if a and b are same if (a == b) { return (check(a * n, a, b)); } int ans = 0; for (int i = 0; i <= n; ++i) { if (check(i * a + (n - i) * b, a, b) == 1) { ans = (ans + comb(n, i)) % mod; } } return ans; } // Driver Code public static void main(String[] args) { int a = 3, b = 4, n = 11028; System.out.println(count(a, b, n)); }} // This code is contributed by PrinciRaj1992 |
Python3
# Python 3 program to count the # number of numbers formed by # digits a and b exactly of a # length N such that the sum of # the digits of the number thus # formed is of digits a and b.mod = 1000000007N = 1000005fact = [0] * Ninvfact = [0] * N# function to check if sum of# digits is made of a and bdef check(x, a, b): # sum of digits is 0 if (x == 0): return 0 while (x) : # if any of digits in sum # is other than a and b if (x % 10 != a and x % 10 != b): return 0 x //= 10 return 1# calculate the modInverse V of# a number in O(log n)def modInverse(a, m): m0 = m y = 0 x = 1 if (m == 1): return 0 while (a > 1) : # q is quotient q = a // m t = m # m is remainder now, process # same as Euclid's algo m = a % m a = t t = y # Update y and x y = x - q * y x = t # Make x positive if (x < 0): x += m0 return x# function to pregenerate factorialsdef pregenFact(): fact[0] = fact[1] = 1 for i in range(1, 1000001): fact[i] = fact[i - 1] * i % mod# function to pre calculate the# modInverse of factorialsdef pregenInverse(): invfact[0] = invfact[1] = 1 # calculates the modInverse of # the last factorial invfact[1000000] = modInverse(fact[1000000], mod) # precalculates the modInverse # of all factorials by formulae for i in range(999999, 0, -1): invfact[i] = ((invfact[i + 1] * (i + 1)) % mod)# function that returns# the value of nCidef comb(big, small): return (fact[big] * invfact[small] % mod * invfact[big - small] % mod)# function that returns the # count of numbersdef count(a, b, n): # function call to pre-calculate # the factorials and modInverse # of factorials pregenFact() pregenInverse() # if a and b are same if (a == b) : return (check(a * n, a, b)) ans = 0 for i in range(n + 1) : if (check(i * a + (n - i) * b, a, b)) : ans = (ans + comb(n, i)) % mod return ans# Driver Codeif __name__=="__main__": a = 3 b = 4 n = 11028 print(count(a, b, n))# This code is contributed # by ChitraNayal |
C#
// C# program to count the number// of numbers formed by digits a// and b exactly of a length N such// that the sum of the digits of the// number thus formed is of digits a and b.using System;class GFG { static int mod = (int) (1e9 + 7); static int N = 1000005; static int []fact = new int[N]; static int []invfact = new int[N]; // function to check if sum of // digits is made of a and b static int check(int x, int a, int b) { // sum of digits is 0 if (x == 0) { return 0; } while (x > 0) { // if any of digits in sum is // other than a and b if (x % 10 != a & x % 10 != b) { return 0; } x /= 10; } return 1; } // calculate the modInverse V / of a number in O(log n) static int modInverse(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) { return 0; } while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process // same as Euclid's algo m = a % m; a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) { x += m0; } return x; } // function to pregenerate factorials static void pregenFact() { fact[0] = fact[1] = 1; for (int i = 1; i <= 1000000; ++i) { fact[i] = (int) ((long) fact[i - 1] * i % mod); } } // function to pre calculate the // modInverse of factorials static void pregenInverse() { invfact[0] = invfact[1] = 1; // calculates the modInverse of // the last factorial invfact[1000000] = modInverse(fact[1000000], mod); // precalculates the modInverse of // all factorials by formulae for (int i = 999999; i > 1; --i) { invfact[i] = (int) (((long) invfact[i + 1] * (long) (i + 1)) % mod); } } // function that returns the value of nCi static int comb(int big, int small) { return (int) ((long) fact[big] * invfact[small] % mod * invfact[big - small] % mod); } // function that returns the count of numbers static int count(int a, int b, int n) { // function call to pre-calculate the // factorials and modInverse of factorials pregenFact(); pregenInverse(); // if a and b are same if (a == b) { return (check(a * n, a, b)); } int ans = 0; for (int i = 0; i <= n; ++i) { if (check(i * a + (n - i) * b, a, b) == 1) { ans = (ans + comb(n, i)) % mod; } } return ans; } // Driver Code public static void Main(String[] args) { int a = 3, b = 4, n = 11028; Console.WriteLine(count(a, b, n)); }}// This code has been contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to count the number // of numbers formed by digits a // and b exactly of a length N such // that the sum of the digits of the // number thus formed is of digits a and b. const mod = 1000000007; const N = 1000005; let fact = new Array(N).fill(0); let invfact = new Array(N).fill(0); // function to check if sum of // digits is made of a and b const check = (x, a, b) => { // sum of digits is 0 if (x == 0) return 0; while (x) { // if any of digits in sum is // other than a and b if (x % 10 != a && x % 10 != b) return 0; x = Math.floor(x / 10); } return 1; } // calculate the modInverse V / of a number in O(log n) const modInverse = (a, m) => { let m0 = m; let y = 0, x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient let q = Math.floor(a / m); let t = m; // m is remainder now, process // same as Euclid's algo m = a % m; a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // function to pregenerate factorials const pregenFact = () => { fact[0] = 1; fact[1] = 1; for (let i = 1; i <= 1000000; ++i) fact[i] = fact[i - 1] * i % mod; } // function to pre calculate the // modInverse of factorials const pregenInverse = () => { invfact[0] = 1; invfact[1] = 1; // calculates the modInverse of the last factorial invfact[1000000] = modInverse(fact[1000000], mod); // precalculates the modInverse of all factorials // by formulae for (let i = 999999; i > 1; --i) invfact[i] = (invfact[i + 1] * (i + 1)) % mod; } // function that returns the value of nCi let comb = (big, small) => { return ((BigInt(fact[big]) * BigInt(invfact[small])) % BigInt(mod) * BigInt(invfact[big - small]) % BigInt(mod)) % BigInt(mod); } // function that returns the count of numbers const count = (a, b, n) => { // function call to pre-calculate the // factorials and modInverse of factorials pregenFact(); pregenInverse(); // if a and b are same if (a == b) return (check(a * n, a, b)); let ans = 0n; for (let i = 0; i <= n; ++i) if (check(i * a + (n - i) * b, a, b)) { ans = (ans + comb(n, i)) % BigInt(mod); } return ans; } // Driver Code let a = 3, b = 4, n = 11028; document.write(count(a, b, n));// This code is contributed by rakeshsahni</script> |
Output:
461668105
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!
