Data Modelling & AI Data Structure & Algorithm

Count of N digit Numbers having no pair of equal consecutive Digits

23 June 2025

0

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 = 81

Input: 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 digits
void 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 Code
int main()
{
    int N = 2;
     
    count(N);
    return 0;
}
 
// This code is contributed by rutvik_56

Java

// Java Program to implement
// the above approach
import 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 digits
def 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 Code
if __name__ == '__main__':
    N = 2;
    count(N);
 
# This code is contributed by sapnasingh4991

C#

// C# program to implement
// the above approach
using 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;
    }
 
    // 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 Code
public 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 digits
function 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 Code
var N = 2;
 
count(N);
 
// This code is contributed by itsok
 
</script>

Output:

Time Complexity: O(N * (10^N), 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 digits
void 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 Code
int main()
{
  int N = 2;
  count(N);
  return 0;
}
 
// This code is contributed by sapnasingh4991

Java

// Java Program to implement
// of the above approach
import 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 digits
def 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 Code
if __name__ == '__main__':
    N = 2;
    count(N);
 
# This code is contributed by Amit Katiyar

C#

// C# Program to implement
// of the above approach
using 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 digits
function 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 Code
var N = 2;
 
count(N);
 
// This code is contributed by noob2000
 
</script>

Output:

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 9^N 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 digits
void count(int N)
{
 
    // Base Case
    if (N == 1) 
    {
        cout << 10 << endl;
        return;
    }
 
    cout << (power(9, N, 1000000007)) << endl;
}
 
// Driver Code
int main()
{
    int N = 3;
    count(N);
    return 0;
}
 
// This code is contributed by sapnasingh4991

Java

// Java Program to implement
// of the above approach
import 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 digits
def count(N):
   
    # Base Case
    if (N == 1):
        print(10);
        return;
 
    print(power(9, N, 1000000007));
 
# Driver Code
if __name__ == '__main__':
    N = 3;
    count(N);
 
# This code is contributed by Rohit_ranjan

C#

// C# program to implement
// of the above approach
using 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 digits
public static void count(int N)
{
 
    // Base Case
    if (N == 1) 
    {
        Console.WriteLine(10);
        return;
    }
 
    Console.WriteLine(power(9, N,
                            1000000007));
}
 
// Driver Code
public 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 digits
function count(N)
{
     
    // Base Case
    if (N == 1)
    {
        document.write(10);
        return;
    }
    document.write(power(9, N, 1000000007));
}
 
// Driver Code
let N = 3;
 
count(N);
 
// this code is contributed by shivanisinghss2110 
 
</script>

Output:

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!

Count of N digit Numbers having no pair of equal consecutive Digits

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Bringing Geospatial Filtering and Vector Search Together with Geometry Fields and RTREE in Milvus 2.6

Introducing AISAQ in Milvus: Billion-Scale Vector Search Just Got 3,200× Cheaper on Memory

Optimizing NVIDIA CAGRA in Milvus: A Hybrid GPU–CPU Approach to Faster Indexing and Cheaper Queries

LEAVE A REPLY Cancel reply

Most Popular

You can finally stop unknown senders from sliding into your Google Chat DMs

Wear OS gains a powerful tool that can help you when panic strikes

Google just upgraded your Gemini app with a faster default model

The subtle reason why the iPhone Air is a serious problem for Google

EDITOR PICKS

You can finally stop unknown senders from sliding into your Google Chat DMs

Wear OS gains a powerful tool that can help you when panic strikes

Google just upgraded your Gemini app with a faster default model

POPULAR POSTS

You can finally stop unknown senders from sliding into your Google Chat DMs

Wear OS gains a powerful tool that can help you when panic strikes

Google just upgraded your Gemini app with a faster default model

POPULAR CATEGORY

ABOUT US

FOLLOW US