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