Numbers of Length N having digits A and B and whose sum of digits contain only digits A and B

0 0 12 minutes read

Given three positive integers N, A, and B. The task is to count the numbers of length N containing only digits A and B and whose sum of digits also contains the digits A and B only. Print the answer modulo 10⁹ + 7.
Examples:

Input: N = 3, A = 1, B = 3
Output: 1
Possible numbers of length 3 are 113, 131, 111, 333, 311, 331 and so on…
But only 111 is a valid number since its sum of digits is 3 (contains digits A and B only)

Input: N = 10, A = 2, B = 3
Output: 165

Approach: The idea is to express the sum of digits of the number as a linear equation in two variables i.e.
S = X * A + Y * B where A and B are the given digits and X and Y are the frequencies of these digits respectively.
Since, the sum of (X + Y) should be equal to N (length of the number) according to the given condition, we can replace Y with (N – X) and the equation reduces to S = X * A + (N – X) * B. Thus, X = (S – N * B) / (A – B).
Now, we can iterate over all possible values of S where minimum value of S is an N-digit number where all digits are 1 and maximum value of S is an N-digit number where all digits are 9 and check if the current value contains only digits A and B. Find the values of X and Y using the above formula for valid current S. Since, we can also permute the digits count of numbers will be (N! / X! Y!) for current value S. Add this result to the final answer.
Note: Use Fermat Little Theorem to compute n! % p.

Steps to solve the problem:

Initialize fact[MAX] and inv[MAX] arrays with all elements set to 0 and initialize ans to 0.
Generate factorials of all numbers from 0 to MAX-1 and store them in the fact array.
Generate inverses of factorials modulo MOD of all numbers from MAX-1 to 0 and store them in the inv array.
If a is less than b, swap their values.
- Iterate through s from n to 9n:
- If check(s, a, b) returns false, continue to the next value of s.
- If s is less than n times b or if (s – n * b) modulo (a – b) is not equal to 0, continue to the next value of s.
- Calculate numDig as (s – n * b) divided by (a – b).
- If numDig is greater than n, continue to the next value of s.
- Calculate curr as follows:
  - Set curr to fact[n].
  - Multiply curr by inv[numDig] modulo MOD.
  - Multiply curr by inv[n – numDig] modulo MOD.
- Add curr to ans modulo MOD.
Return ans as the required answer.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
#define ll long long
 
// Function that returns true if the num contains
// a and b digits only
int check(int num, int a, int b)
{
    while (num) {
        int rem = num % 10;
        num /= 10;
        if (rem != a && rem != b)
            return 0;
    }
    return 1;
}
 
// Modular Exponentiation
ll power(ll x, ll y)
{
    ll ans = 1;
    while (y) {
        if (y & 1)
            ans = (ans * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return ans % MOD;
}
 
// Function to return the modular inverse
// of x modulo MOD
int modInverse(int x)
{
    return power(x, MOD - 2);
}
 
// Function to return the required count
// of numbers
ll countNumbers(int n, int a, int b)
{
    ll fact[MAX], inv[MAX];
    ll ans = 0;
 
    // Generating factorials of all numbers
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = (1LL * fact[i - 1] * i);
        fact[i] %= MOD;
    }
 
    // Generating inverse of factorials modulo
    // MOD of all numbers
    inv[MAX - 1] = modInverse(fact[MAX - 1]);
    for (int i = MAX - 2; i >= 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1));
        inv[i] %= MOD;
    }
 
    // Keeping a as largest number
    if (a < b)
        swap(a, b);
 
    // Iterate over all possible values of s and
    // if it is a valid S then proceed further
    for (int s = n; s <= 9 * n; s++) {
        if (!check(s, a, b))
            continue;
 
        // Check for invalid cases in the equation
        if (s < n * b || (s - n * b) % (a - b) != 0)
            continue;
        int numDig = (s - n * b) / (a - b);
        if (numDig > n)
            continue;
 
        // Find answer using combinatorics
        ll curr = fact[n];
        curr = (curr * inv[numDig]) % MOD;
        curr = (curr * inv[n - numDig]) % MOD;
 
        // Add this result to final answer
        ans = (ans + curr) % MOD;
    }
    return ans;
}
 
// Driver Code
int main()
{
    int n = 3, a = 1, b = 3;
    cout << countNumbers(n, a, b);
 
    return 0;
}

C

// C implementation of the approach
#include <stdio.h>
#include<math.h>
 
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
#define ll long long
 
// Function that returns true if the num contains
// a and b digits only
int check(int num, int a, int b)
{
    while (num) {
        int rem = num % 10;
        num /= 10;
        if (rem != a && rem != b)
            return 0;
    }
    return 1;
}
 
// Modular Exponentiation
ll power(ll x, ll y)
{
    ll ans = 1;
    while (y) {
        if (y & 1)
            ans = (ans * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return ans % MOD;
}
 
// Function to return the modular inverse
// of x modulo MOD
int modInverse(int x)
{
    return power(x, MOD - 2);
}
 
// Function to return the required count
// of numbers
ll countNumbers(int n, int a, int b)
{
    ll fact[MAX], inv[MAX];
    ll ans = 0;
 
    // Generating factorials of all numbers
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = (1LL * fact[i - 1] * i);
        fact[i] %= MOD;
    }
 
    // Generating inverse of factorials modulo
    // MOD of all numbers
    inv[MAX - 1] = modInverse(fact[MAX - 1]);
    for (int i = MAX - 2; i >= 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1));
        inv[i] %= MOD;
    }
 
    // Keeping a as largest number
    if (a < b){
        //Swapping a and b
        a=a+b;    
        b=a-b;
        a=a-b;
    }
         
 
    // Iterate over all possible values of s and
    // if it is a valid S then proceed further
    for (int s = n; s <= 9 * n; s++) {
        if (!check(s, a, b))
            continue;
 
        // Check for invalid cases in the equation
        if (s < n * b || (s - n * b) % (a - b) != 0)
            continue;
        int numDig = (s - n * b) / (a - b);
        if (numDig > n)
            continue;
 
        // Find answer using combinatorics
        ll curr = fact[n];
        curr = (curr * inv[numDig]) % MOD;
        curr = (curr * inv[n - numDig]) % MOD;
 
        // Add this result to final answer
        ans = (ans + curr) % MOD;
    }
    return ans;
}
 
// Driver Code
int main()
{
    int n = 3, a = 1, b = 3;
    printf("%lld",countNumbers(n, a, b));
 
    return 0;
}
 
// This code is contributed by allwink45.

Java

// Java implementation of the approach
 
class GFG
{
     
static int MAX = (int)(1E5 + 5);
static long MOD = (long)(1E9 + 7);
 
// Function that returns true if the num contains
// a and b digits only
static boolean check(long num, long a, long b)
{
    while (num > 0) 
    {
        long rem = num % 10;
        num /= 10;
        if (rem != a && rem != b)
            return false;
    }
    return true;
}
 
// Modular Exponentiation
static long power(long x, long y)
{
    long ans = 1;
    while (y > 0) 
    {
        if ((y & 1) > 0)
            ans = (ans * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return ans % MOD;
}
 
// Function to return the modular inverse
// of x modulo MOD
static long modInverse(long x)
{
    return power(x, MOD - 2);
}
 
// Function to return the required count
// of numbers
static long countNumbers(long n, long a, long b)
{ 
    long[] fact = new long[MAX];
    long[] inv = new long[MAX];
    long ans = 0;
 
    // Generating factorials of all numbers
    fact[0] = 1;
    for (int i = 1; i < MAX; i++)
    {
        fact[i] = (1 * fact[i - 1] * i);
        fact[i] %= MOD;
    }
 
    // Generating inverse of factorials modulo
    // MOD of all numbers
    inv[MAX - 1] = modInverse(fact[MAX - 1]);
    for (int i = MAX - 2; i >= 0; i--)
    {
        inv[i] = (inv[i + 1] * (i + 1));
        inv[i] %= MOD;
    }
 
    // Keeping a as largest number
    if (a < b)
    {
        long x = a;
        a = b;
        b = x;
    }
 
    // Iterate over all possible values of s and
    // if it is a valid S then proceed further
    for (long s = n; s <= 9 * n; s++)
    {
        if (!check(s, a, b))
            continue;
 
        // Check for invalid cases in the equation
        if (s < n * b || (s - n * b) % (a - b) != 0)
            continue;
        int numDig = (int)((s - n * b) / (a - b));
        if (numDig > n)
            continue;
 
        // Find answer using combinatorics
        long curr = fact[(int)n];
        curr = (curr * inv[numDig]) % MOD;
        curr = (curr * inv[(int)n - numDig]) % MOD;
 
        // Add this result to final answer
        ans = (ans + curr) % MOD;
    }
    return ans;
}
 
// Driver Code
public static void main (String[] args) 
{
    long n = 3, a = 1, b = 3;
    System.out.println(countNumbers(n, a, b));
}
}
 
// This code is contributed by mits

Python3

# Python 3 implementation of the approach
MAX = 100005;
MOD = 1000000007
 
# Function that returns true if the num 
# contains a and b digits only
def check(num, a, b):
    while (num):
        rem = num % 10
        num = int(num / 10)
        if (rem != a and rem != b):
            return 0
     
    return 1
 
# Modular Exponentiation
def power(x, y):
    ans = 1
    while (y):
        if (y & 1):
            ans = (ans * x) % MOD
        y >>= 1
        x = (x * x) % MOD
 
    return ans % MOD
 
# Function to return the modular 
# inverse of x modulo MOD
def modInverse(x):
    return power(x, MOD - 2)
 
# Function to return the required 
# count of numbers
def countNumbers(n, a, b):
    fact = [0 for i in range(MAX)]
    inv = [0 for i in range(MAX)]
    ans = 0
 
    # Generating factorials of all numbers
    fact[0] = 1
    for i in range(1, MAX, 1):
        fact[i] = (1 * fact[i - 1] * i)
        fact[i] %= MOD
 
    # Generating inverse of factorials 
    # modulo MOD of all numbers
    inv[MAX - 1] = modInverse(fact[MAX - 1])
    i = MAX - 2
    while(i >= 0):
        inv[i] = (inv[i + 1] * (i + 1))
        inv[i] %= MOD
        i -= 1
 
    # Keeping a as largest number
    if (a < b):
        temp = a
        a = b
        b = temp
 
    # Iterate over all possible values of s and
    # if it is a valid S then proceed further
    for s in range(n, 9 * n + 1, 1):
        if (check(s, a, b) == 0):
            continue
 
        # Check for invalid cases in the equation
        if (s < n * b or (s - n * b) % (a - b) != 0):
            continue
        numDig = int((s - n * b) / (a - b))
        if (numDig > n):
            continue
 
        # Find answer using combinatorics
        curr = fact[n]
        curr = (curr * inv[numDig]) % MOD
        curr = (curr * inv[n - numDig]) % MOD
 
        # Add this result to final answer
        ans = (ans + curr) % MOD
 
    return ans
 
# Driver Code
if __name__ == '__main__':
    n = 3
    a = 1
    b = 3
    print(countNumbers(n, a, b))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
static long MAX = (long)(1E5 + 5);
static long MOD = (long)(1E9 + 7);
 
// Function that returns true if the num contains
// a and b digits only
static bool check(long num, long a, long b)
{
    while (num > 0) 
    {
        long rem = num % 10;
        num /= 10;
        if (rem != a && rem != b)
            return false;
    }
    return true;
}
 
// Modular Exponentiation
static long power(long x, long y)
{
    long ans = 1;
    while (y > 0) 
    {
        if ((y & 1) > 0)
            ans = (ans * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return ans % MOD;
}
 
// Function to return the modular inverse
// of x modulo MOD
static long modInverse(long x)
{
    return power(x, MOD - 2);
}
 
// Function to return the required count
// of numbers
static long countNumbers(long n, long a, long b)
{ 
    long[] fact = new long[MAX];
    long[] inv = new long[MAX];
    long ans = 0;
 
    // Generating factorials of all numbers
    fact[0] = 1;
    for (long i = 1; i < MAX; i++)
    {
        fact[i] = (1 * fact[i - 1] * i);
        fact[i] %= MOD;
    }
 
    // Generating inverse of factorials modulo
    // MOD of all numbers
    inv[MAX - 1] = modInverse(fact[MAX - 1]);
    for (long i = MAX - 2; i >= 0; i--)
    {
        inv[i] = (inv[i + 1] * (i + 1));
        inv[i] %= MOD;
    }
 
    // Keeping a as largest number
    if (a < b)
    {
        long x = a;
        a = b;
        b = x;
    }
 
    // Iterate over all possible values of s and
    // if it is a valid S then proceed further
    for (long s = n; s <= 9 * n; s++)
    {
        if (!check(s, a, b))
            continue;
 
        // Check for invalid cases in the equation
        if (s < n * b || (s - n * b) % (a - b) != 0)
            continue;
        long numDig = (s - n * b) / (a - b);
        if (numDig > n)
            continue;
 
        // Find answer using combinatorics
        long curr = fact[n];
        curr = (curr * inv[numDig]) % MOD;
        curr = (curr * inv[n - numDig]) % MOD;
 
        // Add this result to final answer
        ans = (ans + curr) % MOD;
    }
    return ans;
}
 
// Driver Code
static void Main()
{
    long n = 3, a = 1, b = 3;
    Console.WriteLine(countNumbers(n, a, b));
}
}
 
// This code is contributed by mits

Javascript

<script>
 
// JavaScript implementation of the approach
    const MAX = (5);
    let MOD =  (7);
 
    // Function that returns true if the num contains
    // a and b digits only
    function check(num , a , b) {
        while (num > 0) {
            var rem = num % 10;
            num = parseInt(num/10);
            if (rem != a && rem != b)
                return false;
        }
        return true;
    }
 
    // Modular Exponentiation
    function power(x , y) {
        var ans = 1;
        while (y > 0) {
            if ((y & 1) > 0)
                ans = (ans * x) % MOD;
            y >>= 1;
            x = (x * x) % MOD;
        }
        return ans % MOD;
    }
 
    // Function to return the modular inverse
    // of x modulo MOD
    function modInverse(x) {
        return power(x, MOD - 2);
    }
 
    // Function to return the required count
    // of numbers
    function countNumbers(n , a , b) {
        var fact = Array(MAX).fill(0);
        var inv = Array(MAX).fill(0);
        var ans = 0;
 
        // Generating factorials of all numbers
        fact[0] = 1;
        for (var i = 1; i < MAX; i++) {
            fact[i] = (1 * fact[i - 1] * i);
            fact[i] %= MOD;
        }
 
        // Generating inverse of factorials modulo
        // MOD of all numbers
        inv[MAX - 1] = modInverse(fact[MAX - 1]);
        for (i = MAX - 2; i >= 0; i--) {
            inv[i] = (inv[i + 1] * (i + 1));
            inv[i] %= MOD;
        }
 
        // Keeping a as largest number
        if (a < b) {
            var x = a;
            a = b;
            b = x;
        }
 
        // Iterate over all possible values of s and
        // if it is a valid S then proceed further
        for (s = n; s <= 9 * n; s++) {
            if (!check(s, a, b))
                continue;
 
            // Check for invalid cases in the equation
            if (s < n * b || (s - n * b) % (a - b) != 0)
                continue;
            var numDig = parseInt( ((s - n * b) / (a - b)));
            if (numDig > n)
                continue;
 
            // Find answer using combinatorics
            var curr = fact[parseInt(n)];
            curr = (curr * inv[numDig]) % MOD;
            curr = (curr * inv[parseInt( n - numDig)]) % MOD;
 
            // Add this result to final answer
            ans = (ans + curr) % MOD;
        }
        return ans;
    }
 
    // Driver Code
     
        var n = 3, a = 1, b = 3;
        document.write(countNumbers(n, a, b));
 
 
// This code contributed by umadevi9616 
 
</script>

Output

Time Complexity: O(Max)
Auxiliary Space: O(Max), since Max extra space has been taken.

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!