Dada una string que contiene dígitos de un número. El número puede contener muchos dígitos continuos iguales. La tarea es contar el número de formas de deletrear el número.
Por ejemplo, considere 8884441100, se puede deletrear simplemente como triple ocho triple cuatro doble dos y doble cero. También se puede escribir como doble ocho, ocho, cuatro, doble cuatro, dos, dos, doble cero.
Ejemplos:
Input : num = 100 Output : 2 The number 100 has only 2 possibilities, 1) one zero zero 2) one double zero. Input : num = 11112 Output: 8 1 1 1 1 2, 11 1 1 2, 1 1 11 2, 1 11 1 2 11 11 2, 1 111 2, 111 1 2, 1111 2 Input : num = 8884441100 Output: 64 Input : num = 12345 Output: 1 Input : num = 11111 Output: 16
Este es un problema simple de permutación y combinación. Si tomamos el caso de prueba de ejemplo dado en la pregunta, 11112. La respuesta depende de la cantidad de posibles substrings de 1111. La cantidad de posibles substrings de «1111» es 2^3 = 8 porque es la cantidad de combinaciones de 4: 1 = 3 separadores ‘|’ entre dos caracteres de la string (dígitos del número representado por la string): “1|1|1|1”. Como nuestras combinaciones dependerán de si elegimos un 1 en particular y para «2» solo habrá una posibilidad 2^0 = 1, entonces la respuesta para «11112» será 8*1 = 8.
Entonces, el enfoque es contar el dígito continuo particular en la string y multiplicar 2^(contar-1) con el resultado anterior.
C++
// C++ program to count number of ways we
// can spell a number
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Function to calculate all possible spells of
// a number with repeated digits
// num --> string which is favourite number
ll spellsCount(string num)
{
int n = num.length();
// final count of total possible spells
ll result = 1;
// iterate through complete number
for (int i=0; i<n; i++)
{
// count contiguous frequency of particular
// digit num[i]
int count = 1;
while (i < n-1 && num[i+1] == num[i])
{
count++;
i++;
}
// Compute 2^(count-1) and multiply with result
result = result * pow(2, count-1);
}
return result;
}
// Driver program to run the case
int main()
{
string num = "11112";
cout << spellsCount(num);
return 0;
}
Java
// Java program to count number of ways we
// can spell a number
class GFG {
// Function to calculate all possible
// spells of a number with repeated digits
// num --> string which is favourite number
static long spellsCount(String num)
{
int n = num.length();
// final count of total possible spells
long result = 1;
// iterate through complete number
for (int i = 0; i < n; i++) {
// count contiguous frequency of
// particular digit num[i]
int count = 1;
while (i < n - 1 && num.charAt(i + 1)
== num.charAt(i)) {
count++;
i++;
}
// Compute 2^(count-1) and multiply
// with result
result = result *
(long)Math.pow(2, count - 1);
}
return result;
}
public static void main(String[] args)
{
String num = "11112";
System.out.print(spellsCount(num));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to count number of # ways we can spell a number # Function to calculate all possible # spells of a number with repeated # digits num --> string which is # favourite number def spellsCount(num): n = len(num); # final count of total # possible spells result = 1; # iterate through complete # number i = 0; while(i<n): # count contiguous frequency # of particular digit num[i] count = 1; while (i < n - 1 and num[i + 1] == num[i]): count += 1; i += 1; # Compute 2^(count-1) and # multiply with result result = result * int(pow(2, count - 1)); i += 1; return result; # Driver Code num = "11112"; print(spellsCount(num)); # This code is contributed # by mits
C#
// C# program to count number of ways we
// can spell a number
using System;
class GFG {
// Function to calculate all possible
// spells of a number with repeated
// digits num --> string which is
// favourite number
static long spellsCount(String num)
{
int n = num.Length;
// final count of total possible
// spells
long result = 1;
// iterate through complete number
for (int i = 0; i < n; i++)
{
// count contiguous frequency of
// particular digit num[i]
int count = 1;
while (i < n - 1 && num[i + 1]
== num[i])
{
count++;
i++;
}
// Compute 2^(count-1) and multiply
// with result
result = result *
(long)Math.Pow(2, count - 1);
}
return result;
}
// Driver code
public static void Main()
{
String num = "11112";
Console.Write(spellsCount(num));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to count
// number of ways we
// can spell a number
// Function to calculate
// all possible spells of
// a number with repeated
// digits num --> string
// which is favourite number
function spellsCount($num)
{
$n = strlen($num);
// final count of total
// possible spells
$result = 1;
// iterate through
// complete number
for ($i = 0; $i < $n; $i++)
{
// count contiguous frequency
// of particular digit num[i]
$count = 1;
while ($i < $n - 1 &&
$num[$i + 1] == $num[$i])
{
$count++;
$i++;
}
// Compute 2^(count-1) and
// multiply with result
$result = $result *
pow(2, $count - 1);
}
return $result;
}
// Driver Code
$num = "11112";
echo spellsCount($num);
// This code is contributed
// by nitin mittal.
?>
Javascript
<script>
// Javascript program to count number of
// ways we can spell a number
// Function to calculate all possible
// spells of a number with repeated
// digits num --> string which is
// favourite number
function spellsCount(num)
{
let n = num.length;
// Final count of total possible
// spells
let result = 1;
// Iterate through complete number
for (let i = 0; i < n; i++)
{
// Count contiguous frequency of
// particular digit num[i]
let count = 1;
while (i < n - 1 &&
num[i + 1] == num[i])
{
count++;
i++;
}
// Compute 2^(count-1) and multiply
// with result
result = result *
Math.pow(2, count - 1);
}
return result;
}
// Driver code
let num = "11112";
document.write(spellsCount(num));
// This code is contributed by code_hunt
</script>
Producción :
8
Si tiene otro enfoque para resolver este problema, por favor comparta.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA