Recuento de N dígitos Números que no tienen par de dígitos consecutivos iguales

Dado un número entero N , la tarea es encontrar el recuento total de números de N dígitos de modo que no haya dos dígitos consecutivos iguales.

Ejemplos:

Entrada: N = 2 
Salida: 81 
Explicación: 
Cuente los posibles números de 2 dígitos, es decir, los números en el rango [10, 99] = 90 
Todos los números de 2 dígitos que tienen dígitos consecutivos iguales son {11, 22, 33, 44, 55 , 66, 77, 88, 99}. 
Por lo tanto, el conteo requerido = 90 – 9 = 81

Entrada: N = 1
Salida: 10

Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre todos los números posibles de N dígitos y verificar para cada número si dos dígitos consecutivos son iguales o no.

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

81

 

Complejidad de tiempo: O(N * (10 N ), donde N es el número entero dado.  
Espacio auxiliar: O(1)

Enfoque de programación dinámica: el enfoque anterior se puede optimizar utilizando el enfoque de programación dinámica . Siga los pasos a continuación para resolver el problema:

  • Inicialice DP[][] , donde DP[i][j] almacena el recuento de números que tienen i dígitos y terminan en j .
  • Iterar de 2 a N y seguir los pasos: 
    • Calcule el recuento total de números de dígitos i-1 válidos sumando todos los valores de DP[i-1][j] donde j va de 0 a 9 y guárdelo en temp .
    • Actualice DP[i][j] = temp – DP[i-1][j] , donde j varía de 0 a 9 .
  • El resultado es la suma de DP[N][j] , donde j varía de 0 a 9

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

81

 

Complejidad de tiempo: O(N), donde N es el número entero dado
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar aún más al observar que para cualquier número de N dígitos, la respuesta requerida es 9 N , que se puede calcular mediante exponenciación binaria .

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

729

 

Complejidad de tiempo: O(logN)
Complejidad de espacio: O(1) 

Publicación traducida automáticamente

Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *