Given an integer N, the task is to find the total count of N digit numbers such that no two consecutive digits are equal.
Examples:
Input: N = 2
Output: 81
Explanation:
Count possible 2-digit numbers, i.e. the numbers in the range [10, 99] = 90
All 2-digit numbers having equal consecutive digits are {11, 22, 33, 44, 55, 66, 77, 88, 99}.
Therefore, the required count = 90 – 9 = 81Input: N = 1
Output: 10
Naive Approach: The simplest approach to solve the problem is to iterate over all possible N-digit numbers and check for every number if any two consecutive digits are equal or not.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include<bits/stdc++.h>using namespace std;// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitsvoid count(int N){ // Base Case if (N == 1) { cout << 10 << endl; return; } // Lowest N-digit number int l = pow(10, N - 1); // Highest N-digit number int r = pow(10, N) - 1; // Stores the count of all // required numbers int ans = 0; // Iterate over all N-digit numbers for(int i = l; i <= r; i++) { string s = to_string(i); int flag = 0; // Iterate over all digits for(int j = 1; j < N; j++) { // Check for equal pair of // adjacent digits if (s[j] == s[j - 1]) { flag = 1; break; } } if (flag == 0) ans++; } cout << ans << endl;}// Driver Codeint main(){ int N = 2; count(N); return 0;}// This code is contributed by rutvik_56 |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG { // Function to count the number // of N-digit numbers with no // equal pair of consecutive digits public static void count(int N) { // Base Case if (N == 1) { System.out.println(10); return; } // Lowest N-digit number int l = (int)Math.pow(10, N - 1); // Highest N-digit number int r = (int)Math.pow(10, N) - 1; // Stores the count of all // required numbers int ans = 0; // Iterate over all N-digit numbers for (int i = l; i <= r; i++) { String s = Integer.toString(i); int flag = 0; // Iterate over all digits for (int j = 1; j < N; j++) { // Check for equal pair of // adjacent digits if (s.charAt(j) == s.charAt(j - 1)) { flag = 1; break; } } if (flag == 0) ans++; } System.out.println(ans); } // Driver Code public static void main(String[] args) { int N = 2; count(N); }} |
Python3
# Python3 Program to implement# the above approach# Function to count the number# of N-digit numbers with no# equal pair of consecutive digitsdef count(N): # Base Case if (N == 1): print(10); return; # Lowest N-digit number l = int(pow(10, N - 1)); # Highest N-digit number r = int(pow(10, N) - 1); # Stores the count of all # required numbers ans = 0; # Iterate over all N-digit numbers for i in range(l, r + 1): s = str(i); flag = 0; # Iterate over all digits for j in range(1, N): # Check for equal pair of # adjacent digits if (s[j] == s[j - 1]): flag = 1; break; if (flag == 0): ans+=1; print(ans);# Driver Codeif __name__ == '__main__': N = 2; count(N);# This code is contributed by sapnasingh4991 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitspublic static void count(int N){ // Base Case if (N == 1) { Console.WriteLine(10); return; } // Lowest N-digit number int l = (int)Math.Pow(10, N - 1); // Highest N-digit number int r = (int)Math.Pow(10, N) - 1; // Stores the count of all // required numbers int ans = 0; // Iterate over all N-digit numbers for(int i = l; i <= r; i++) { String s = i.ToString(); int flag = 0; // Iterate over all digits for(int j = 1; j < N; j++) { // Check for equal pair of // adjacent digits if (s[j] == s[j - 1]) { flag = 1; break; } } if (flag == 0) ans++; } Console.WriteLine(ans);}// Driver Codepublic static void Main(String[] args){ int N = 2; count(N);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to implement// the above approach// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitsfunction count(N){ // Base Case if (N == 1) { document.write(10 + "<br>"); return; } // Lowest N-digit number var l = Math.pow(10, N - 1); // Highest N-digit number var r = Math.pow(10, N) - 1; // Stores the count of all // required numbers var ans = 0; // Iterate over all N-digit numbers for(var i = l; i <= r; i++) { var s = (i.toString()); var flag = 0; // Iterate over all digits for(var j = 1; j < N; j++) { // Check for equal pair of // adjacent digits if (s[j] == s[j - 1]) { flag = 1; break; } } if (flag == 0) ans++; } document.write( ans + "<br>");}// Driver Codevar N = 2;count(N);// This code is contributed by itsok</script> |
Output:
81
Time Complexity: O(N * (10N), where N is the given integer.
Auxiliary Space: O(1)
Dynamic Programming Approach: The above approach can be optimized using Dynamic Programming approach. Follow the steps below to solve the problem:
- Initialize DP[][], where DP[i][j] stores the count of numbers having i digits, and ending with j.
- Iterate from 2 to N and follow the steps:
- Calculate the total count of valid i-1 digit numbers by adding all the values of DP[i-1][j] where j ranges from 0 to 9, and store it in temp.
- Update DP[i][j] = temp – DP[i-1][j], where j ranges from 0 to 9.
- The result is the sum of DP[N][j], where j ranges from 0 to 9
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include<bits/stdc++.h>using namespace std;// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitsvoid count(int N){ // Base Case if (N == 1) { cout << (10) << endl; return; } int dp[N][10]; memset(dp, 0, sizeof(dp)); for (int i = 1; i < 10; i++) dp[0][i] = 1; for (int i = 1; i < N; i++) { // Calculate the total count // of valid (i-1)-digit numbers int temp = 0; for (int j = 0; j < 10; j++) temp += dp[i - 1][j]; // Update dp[][] table for (int j = 0; j < 10; j++) dp[i][j] = temp - dp[i - 1][j]; } // Calculate the count of // required N-digit numbers int ans = 0; for (int i = 0; i < 10; i++) ans += dp[N - 1][i]; cout << ans << endl;}// Driver Codeint main(){ int N = 2; count(N); return 0;}// This code is contributed by sapnasingh4991 |
Java
// Java Program to implement// of the above approachimport java.util.*;class GFG { // Function to count the number // of N-digit numbers with no // equal pair of consecutive digits public static void count(int N) { // Base Case if (N == 1) { System.out.println(10); return; } int dp[][] = new int[N][10]; for (int i = 1; i < 10; i++) dp[0][i] = 1; for (int i = 1; i < N; i++) { // Calculate the total count // of valid (i-1)-digit numbers int temp = 0; for (int j = 0; j < 10; j++) temp += dp[i - 1][j]; // Update dp[][] table for (int j = 0; j < 10; j++) dp[i][j] = temp - dp[i - 1][j]; } // Calculate the count of // required N-digit numbers int ans = 0; for (int i = 0; i < 10; i++) ans += dp[N - 1][i]; System.out.println(ans); } // Driver Code public static void main(String[] args) { int N = 2; count(N); }} |
Python3
# Python3 Program to implement# of the above approach# Function to count the number# of N-digit numbers with no# equal pair of consecutive digitsdef count(N): # Base Case if (N == 1): print(10); return; dp = [[0 for i in range(10)] for j in range(N)] for i in range(1,10): dp[0][i] = 1; for i in range(1, N): # Calculate the total count # of valid (i-1)-digit numbers temp = 0; for j in range(10): temp += dp[i - 1][j]; # Update dp table for j in range(10): dp[i][j] = temp - dp[i - 1][j]; # Calculate the count of # required N-digit numbers ans = 0; for i in range(10): ans += dp[N - 1][i]; print(ans);# Driver Codeif __name__ == '__main__': N = 2; count(N);# This code is contributed by Amit Katiyar |
C#
// C# Program to implement// of the above approachusing System;class GFG{ // Function to count the number // of N-digit numbers with no // equal pair of consecutive digits public static void count(int N) { // Base Case if (N == 1) { Console.WriteLine(10); return; } int [,]dp = new int[N, 10]; for (int i = 1; i < 10; i++) dp[0, i] = 1; for (int i = 1; i < N; i++) { // Calculate the total count // of valid (i-1)-digit numbers int temp = 0; for (int j = 0; j < 10; j++) temp += dp[i - 1, j]; // Update [,]dp table for (int j = 0; j < 10; j++) dp[i, j] = temp - dp[i - 1, j]; } // Calculate the count of // required N-digit numbers int ans = 0; for (int i = 0; i < 10; i++) ans += dp[N - 1, i]; Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { int N = 2; count(N); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to implement// the above approach// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitsfunction count(N){ // Base Case if (N == 1) { document.write((10) + "<br>"); return; } var dp = Array.from(Array(N), ()=> Array(10).fill(0)); for(var i = 1; i < 10; i++) dp[0][i] = 1; for(var i = 1; i < N; i++) { // Calculate the total count // of valid (i-1)-digit numbers var temp = 0; for(var j = 0; j < 10; j++) temp += dp[i - 1][j]; // Update dp[][] table for(var j = 0; j < 10; j++) dp[i][j] = temp - dp[i - 1][j]; } // Calculate the count of // required N-digit numbers var ans = 0; for(var i = 0; i < 10; i++) ans += dp[N - 1][i]; document.write(ans);}// Driver Codevar N = 2;count(N);// This code is contributed by noob2000</script> |
Output:
81
Time Complexity: O(N), where N is the given integer
Auxiliary Space: O(N)
Efficient Approach: The above approach can be further optimized by observing that for any N digit number, the required answer is 9N which can be calculated using Binary Exponentiation.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Iterative Function to calculate// (x^y) % mod in O(log y)int power(int x, int y, int mod){ // Initialize result int res = 1; // Update x if x >= mod x = x % mod; // If x is divisible by mod if (x == 0) return 0; while (y > 0) { // If y is odd, multiply x // with result if ((y & 1) == 1) res = (res * x) % mod; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % mod; } return res;}// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitsvoid count(int N){ // Base Case if (N == 1) { cout << 10 << endl; return; } cout << (power(9, N, 1000000007)) << endl;}// Driver Codeint main(){ int N = 3; count(N); return 0;}// This code is contributed by sapnasingh4991 |
Java
// Java Program to implement// of the above approachimport java.util.*;class GFG { // Iterative Function to calculate // (x^y) % mod in O(log y) static int power(int x, int y, int mod) { // Initialize result int res = 1; // Update x if x >= mod x = x % mod; // If x is divisible by mod if (x == 0) return 0; while (y > 0) { // If y is odd, multiply x // with result if ((y & 1) == 1) res = (res * x) % mod; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % mod; } return res; } // Function to count the number // of N-digit numbers with no // equal pair of consecutive digits public static void count(int N) { // Base Case if (N == 1) { System.out.println(10); return; } System.out.println(power(9, N, 1000000007)); } // Driver Code public static void main(String[] args) { int N = 3; count(N); }} |
Python3
# Python3 Program to implement# of the above approach# Iterative Function to calculate# (x^y) % mod in O(log y)def power(x, y, mod): # Initialize result res = 1; # Update x if x >= mod x = x % mod; # If x is divisible by mod if (x == 0): return 0; while (y > 0): # If y is odd, multiply x # with result if ((y & 1) == 1): res = (res * x) % mod; # y must be even now # y = y / 2 y = y >> 1; x = (x * x) % mod; return res;# Function to count the number# of N-digit numbers with no# equal pair of consecutive digitsdef count(N): # Base Case if (N == 1): print(10); return; print(power(9, N, 1000000007));# Driver Codeif __name__ == '__main__': N = 3; count(N);# This code is contributed by Rohit_ranjan |
C#
// C# program to implement// of the above approachusing System;class GFG{// Iterative Function to calculate// (x^y) % mod in O(log y)static int power(int x, int y, int mod){ // Initialize result int res = 1; // Update x if x >= mod x = x % mod; // If x is divisible by mod if (x == 0) return 0; while (y > 0) { // If y is odd, multiply x // with result if ((y & 1) == 1) res = (res * x) % mod; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % mod; } return res;}// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitspublic static void count(int N){ // Base Case if (N == 1) { Console.WriteLine(10); return; } Console.WriteLine(power(9, N, 1000000007));}// Driver Codepublic static void Main(String[] args){ int N = 3; count(N);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// of the above approach// Iterative Function to calculate// (x^y) % mod in O(log y)function power(x, y, mod){ // Initialize result let res = 1; // Update x if x >= mod x = x % mod; // If x is divisible by mod if (x == 0) return 0; while (y > 0) { // If y is odd, multiply x // with result if ((y & 1) == 1) res = (res * x) % mod; // y must be even now // y = y / 2 y = y >> 1; x = (x * x) % mod; } return res;}// Function to count the number// of N-digit numbers with no// equal pair of consecutive digitsfunction count(N){ // Base Case if (N == 1) { document.write(10); return; } document.write(power(9, N, 1000000007));}// Driver Codelet N = 3;count(N);// this code is contributed by shivanisinghss2110 </script> |
Output:
729
Time Complexity: O(logN)
Space Complexity: 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!
