Count numbers formed by given two digit with sum having given digits

0 0 12 minutes read

Given a, b and N(1 to 10⁶). 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 ${n \choose i}$ 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 ${n \choose i}$ %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 b
int 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 factorials
void 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 factorials
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] = ((long long)invfact[i + 1] * 
                      (long long)(i + 1)) % mod;
}
 
// function that returns the value of nCi
int comb(int big, int small)
{
    return (long long)fact[big] * invfact[small] % mod * 
                              invfact[big - small] % mod;
}
 
// function that returns the count of numbers
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)) 
            ans = (ans + comb(n, i)) % mod;
    return ans;
}
 
// Driver Code
int 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 = 1000000007
N = 1000005
fact = [0] * N
invfact = [0] * N
 
# function to check if sum of
# digits is made of a and b
def 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 factorials
def 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 factorials
def 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 nCi
def comb(big, small):
     
    return (fact[big] * invfact[small] % mod *
                        invfact[big - small] % mod)
 
# function that returns the 
# count of numbers
def 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 Code
if __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 zambiatek!