Given three integers N, X, and Y, the task is to find the count of N-digit numbers that can be formed using digits 0 to 9 satisfying the following conditions:
- Digits X and Y must be present in them.
- The number may contain leading 0s.
Note: Since the answer can be very large, print the answer modulo 109 + 7.
Examples:
Input: N = 2, X = 1, Y = 2
Output: 2
Explanation:
There are only two possible numbers 12 and 21.Input: N = 10, X = 3, Y = 4
Output: 100172994
Approach: The idea is to use permutation and combination techniques to solve the problem. Follow the steps below to solve the problem:
- Total N-digit numbers that possible using digits {0 – 9} is 10N
- Total N-digit numbers that can be formed using digits {0 – 9} – { X } is 9N
- Total N-digit numbers that can be formed using digit {0 – 9} – {X, Y} is 8N
- Total N-digit numbers that contain digit X and Y is the difference between all possible numbers and the numbers which do not contain digit X or Y followed by the summation of the numbers which contain all digits except X and Y. Hence, the answer is 10N – 2 * 9N + 8N.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;// Function for calculate// (x ^ y) % mod in O(log y)long long power(int x, int y){ // Base Condition if (y == 0) return 1; // Transition state of // power Function long long int p = power(x, y / 2) % mod; p = (p * p) % mod; if (y & 1) { p = (x * p) % mod; } return p;}// Function for counting total numbers// that can be formed such that digits// X, Y are present in each numberint TotalNumber(int N){ // Calculate the given expression int ans = (power(10, N) - 2 * power(9, N) + power(8, N) + 2 * mod) % mod; // Return the final answer return ans;}// Driver Codeint main(){ int N = 10, X = 3, Y = 4; cout << TotalNumber(N) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{static int mod = (int)(1e9 + 7);// Function for calculate// (x ^ y) % mod in O(log y)static long power(int x, int y){ // Base Condition if (y == 0) return 1; // Transition state of // power Function int p = (int)(power(x, y / 2) % mod); p = (p * p) % mod; if (y % 2 == 1) { p = (x * p) % mod; } return p;}// Function for counting total numbers// that can be formed such that digits// X, Y are present in each numberstatic int TotalNumber(int N){ // Calculate the given expression int ans = (int)((power(10, N) - 2 * power(9, N) + power(8, N) + 2 * mod) % mod); // Return the final answer return ans;}// Driver Codepublic static void main(String[] args){ int N = 10, X = 3, Y = 4; System.out.print(TotalNumber(N) + "\n");}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approachmod = 1e9 + 7# Function for calculate# (x ^ y) % mod in O(log y)def power(x, y): # Base Condition if (y == 0): return 1 # Transition state of # power Function p = power(x, y // 2) % mod p = (p * p) % mod if (y & 1): p = (x * p) % mod return p# Function for counting total numbers# that can be formed such that digits# X, Y are present in each numberdef TotalNumber(N): # Calculate the given expression ans = (power(10, N) - 2 * power(9, N) + power(8, N) + 2 * mod) % mod # Return the final answer return ans# Driver Codeif __name__ == '__main__': N = 10 X = 3 Y = 4 print(TotalNumber(N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{static int mod = (int)(1e9 + 7);// Function for calculate// (x ^ y) % mod in O(log y)static long power(int x, int y){ // Base Condition if (y == 0) return 1; // Transition state of // power Function int p = (int)(power(x, y / 2) % mod); p = (p * p) % mod; if (y % 2 == 1) { p = (x * p) % mod; } return p;}// Function for counting // total numbers that can be // formed such that digits// X, Y are present in each numberstatic int TotalNumber(int N){ // Calculate the given expression int ans = (int)((power(10, N) - 2 * power(9, N) + power(8, N) + 2 * mod) % mod); // Return the // readonly answer return ans;}// Driver Codepublic static void Main(String[] args){ int N = 10; Console.Write(TotalNumber(N) + "\n");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript Program for the above approachvar mod = 1000000007;// Function for calculate// (x ^ y) % mod in O(log y)function power(x, y){ // Base Condition if (y == 0) return 1; // Transition state of // power Function var p = power(x, y / 2) % mod; p = (p * p) % mod; if (y & 1) { p = (x * p) % mod; } return p;}// Function for counting total numbers// that can be formed such that digits// X, Y are present in each numberfunction TotalNumber(N){ // Calculate the given expression var ans = (power(10, N) - 2 * power(9, N) + power(8, N) + 2 * mod) % mod; // Return the final answer return ans;}// Driver Codevar N = 10, X = 3, Y = 4;document.write( TotalNumber(N));</script> |
Output
100172994
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!
