Dada una string binaria str . La tarea es encontrar el entero positivo más pequeño C tal que la string binaria se pueda cortar en partes C (substrings) y cada substring debe ser una potencia de 5 sin ceros a la izquierda.
Ejemplos:
Entrada: str = «101101101»
Salida: 3
La string «101101101» se puede dividir en tres strings binarias «101», «101», «101»,
cada una de las cuales es una potencia de 5.
Entrada: str = «1111101»
Salida : 1
La string «1111101» se puede dividir en una string binaria «1111101» que es
125 en decimal y una potencia de 5.
Entrada: str = «00000»
Salida: -1
Strings de solo ceros es equivalente a 0 que no es una potencia de 5
Enfoque: Este problema es una variación simple de la subsecuencia creciente más larga .
Iterar desde i = 1 y para cada str[j…i] donde j = 0 & j < i , verificamos si el número formado a partir de str[j..i] es una potencia de 5 y luego actualizamos la array dp[] con el valor del tamaño de corte más bajo posible. Después de confirmar que el número formado por str[j..i] en decimal es una potencia de 5 , calculamos dp[i] = min(dp[i], dp[j] + 1) .
Esta técnica es bastante similar a encontrar la subsecuencia creciente más larga.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
// Function that returns true
// if n is a power of 5
bool ispower(ll n)
{
if (n < 125)
return (n == 1 || n == 5 || n == 25);
if (n % 125 != 0)
return false;
else
return ispower(n / 125);
}
// Function to return the decimal
// value of binary equivalent
ll number(string s, int i, int j)
{
ll ans = 0;
for (int x = i; x < j; x++) {
ans = ans * 2 + (s[x] - '0');
}
return ans;
}
// Function to return the minimum cuts required
int minCuts(string s, int n)
{
int dp[n + 1];
// Allocating memory for dp[] array
memset(dp, n + 1, sizeof(dp));
dp[0] = 0;
// From length 1 to n
for (int i = 1; i <= n; i++) {
// If previous character is '0' then ignore
// to avoid number with leading 0s.
if (s[i - 1] == '0')
continue;
for (int j = 0; j < i; j++) {
// Ignore s[j] = '0' starting numbers
if (s[j] == '0')
continue;
// Number formed from s[j....i]
ll num = number(s, j, i);
// Check for power of 5
if (!ispower(num))
continue;
// Assigning min value to get min cut possible
dp[i] = min(dp[i], dp[j] + 1);
}
}
// (n + 1) to check if all the strings are traversed
// and no divisible by 5 is obtained like 000000
return ((dp[n] < n + 1) ? dp[n] : -1);
}
// Driver code
int main()
{
string s = "101101101";
int n = s.length();
cout << minCuts(s, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true
// if n is a power of 5
static boolean ispower(long n)
{
if (n < 125)
{
return (n == 1 || n == 5 || n == 25);
}
if (n % 125 != 0)
{
return false;
}
else
{
return ispower(n / 125);
}
}
// Function to return the decimal
// value of binary equivalent
static long number(String s, int i, int j)
{
long ans = 0;
for (int x = i; x < j; x++)
{
ans = ans * 2 + (s.charAt(x) - '0');
}
return ans;
}
// Function to return the minimum cuts required
static int minCuts(String s, int n)
{
int[] dp = new int[n + 1];
// Alongocating memory for dp[] array
Arrays.fill(dp, n+1);
dp[0] = 0;
// From length 1 to n
for (int i = 1; i <= n; i++)
{
// If previous character is '0' then ignore
// to avoid number with leading 0s.
if (s.charAt(i - 1) == '0')
{
continue;
}
for (int j = 0; j < i; j++)
{
// Ignore s[j] = '0' starting numbers
if (s.charAt(j) == '0')
{
continue;
}
// Number formed from s[j....i]
long num = number(s, j, i);
// Check for power of 5
if (!ispower(num))
{
continue;
}
// Assigning min value to get min cut possible
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
// (n + 1) to check if all the Strings are traversed
// and no divisible by 5 is obtained like 000000
return ((dp[n] < n + 1) ? dp[n] : -1);
}
// Driver code
public static void main(String[] args)
{
String s = "101101101";
int n = s.length();
System.out.println(minCuts(s, n));
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python 3 implementation of the approach
# Function that returns true
# if n is a power of 5
def ispower( n):
if (n < 125):
return (n == 1 or n == 5 or n == 25)
if (n % 125 != 0):
return 0
else:
return ispower(n // 125)
# Function to return the decimal
# value of binary equivalent
def number(s, i, j):
ans = 0
for x in range( i, j) :
ans = ans * 2 + (ord(s[x]) - ord('0'))
return ans
# Function to return the minimum cuts required
def minCuts(s, n):
# Allocating memory for dp[] array
dp=[n+1 for i in range(n+1)]
dp[0] = 0;
# From length 1 to n
for i in range(1, n+1) :
# If previous character is '0' then ignore
# to avoid number with leading 0s.
if (s[i - 1] == '0'):
continue
for j in range(i) :
# Ignore s[j] = '0' starting numbers
if (s[j] == '0'):
continue
# Number formed from s[j....i]
num = number(s, j, i)
# Check for power of 5
if (not ispower(num)):
continue
# Assigning min value to get min cut possible
dp[i] = min(dp[i], dp[j] + 1)
# (n + 1) to check if all the strings are traversed
# and no divisible by 5 is obtained like 000000
if dp[n] < n + 1:
return dp[n]
else:
return -1
# Driver code
if __name__== "__main__":
s = "101101101"
n = len(s)
print(minCuts(s, n))
# This code is contributed by ChitraNayal
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true
// if n is a power of 5
static Boolean ispower(long n)
{
if (n < 125)
{
return (n == 1 || n == 5 || n == 25);
}
if (n % 125 != 0)
{
return false;
}
else
{
return ispower(n / 125);
}
}
// Function to return the decimal
// value of binary equivalent
static long number(String s, int i, int j)
{
long ans = 0;
for (int x = i; x < j; x++)
{
ans = ans * 2 + (s[x] - '0');
}
return ans;
}
// Function to return the minimum cuts required
static int minCuts(String s, int n)
{
int[] dp = new int[n + 1];
// Alongocating memory for dp[] array
for (int i = 0; i <= n; i++)
dp[i]=n+1;
dp[0] = 0;
// From length 1 to n
for (int i = 1; i <= n; i++)
{
// If previous character is '0' then ignore
// to avoid number with leading 0s.
if (s[i - 1] == '0')
{
continue;
}
for (int j = 0; j < i; j++)
{
// Ignore s[j] = '0' starting numbers
if (s[j] == '0')
{
continue;
}
// Number formed from s[j....i]
long num = number(s, j, i);
// Check for power of 5
if (!ispower(num))
{
continue;
}
// Assigning min value to get min cut possible
dp[i] = Math.Min(dp[i], dp[j] + 1);
}
}
// (n + 1) to check if all the Strings are traversed
// and no divisible by 5 is obtained like 000000
return ((dp[n] < n + 1) ? dp[n] : -1);
}
// Driver code
public static void Main(String[] args)
{
String s = "101101101";
int n = s.Length;
Console.WriteLine(minCuts(s, n));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
// Function that returns true
// if n is a power of 5
function ispower($n)
{
if ($n < 125)
return ($n == 1 || $n == 5 || $n == 25);
if ($n % 125 != 0)
return false;
else
return ispower($n / 125);
}
// Function to return the decimal
// value of binary equivalent
function number($s, $i, $j)
{
$ans = 0;
for ($x = $i; $x < $j; $x++)
{
$ans = $ans * 2 + (ord($s[$x]) - ord('0'));
}
return $ans;
}
// Function to return the minimum cuts required
function minCuts($s, $n)
{
// Allocating memory for dp[] array
$dp = array_fill(0,$n + 1,$n + 1);
$dp[0] = 0;
// From length 1 to n
for ($i = 1; $i <= $n; $i++)
{
// If previous character is '0' then ignore
// to avoid number with leading 0s.
if ($s[$i - 1] == '0')
continue;
for ($j = 0; $j < $i; $j++)
{
// Ignore s[j] = '0' starting numbers
if ($s[$j] == '0')
continue;
// Number formed from s[j....i]
$num = number($s, $j, $i);
// Check for power of 5
if (!ispower($num))
continue;
// Assigning min value to get min cut possible
$dp[$i] = min($dp[$i], $dp[$j] + 1);
}
}
// (n + 1) to check if all the strings are traversed
// and no divisible by 5 is obtained like 000000
return (($dp[$n] < $n + 1) ? $dp[$n] : -1);
}
// Driver code
$s = "101101101";
$n = strlen($s);
echo minCuts($s, $n);
// This code is contributed by AnkitRai01
?>
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true
// if n is a power of 5
function ispower(n)
{
if (n < 125)
return (n == 1 || n == 5 || n == 25);
if (n % 125 != 0)
return false;
else
return ispower(parseInt(n / 125));
}
// Function to return the decimal
// value of binary equivalent
function number(s, i, j)
{
var ans = 0;
for (var x = i; x < j; x++) {
ans = ans * 2 + (s[x] - '0');
}
return ans;
}
// Function to return the minimum cuts required
function minCuts(s, n)
{
var dp = Array(n+1).fill(n+1);
dp[0] = 0;
// From length 1 to n
for (var i = 1; i <= n; i++) {
// If previous character is '0' then ignore
// to avoid number with leading 0s.
if (s[i - 1] == '0')
continue;
for (var j = 0; j < i; j++) {
// Ignore s[j] = '0' starting numbers
if (s[j] == '0')
continue;
// Number formed from s[j....i]
var num = number(s, j, i);
// Check for power of 5
if (!ispower(num))
continue;
// Assigning min value to get min cut possible
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
// (n + 1) to check if all the strings are traversed
// and no divisible by 5 is obtained like 000000
return ((dp[n] < n + 1) ? dp[n] : -1);
}
// Driver code
var s = "101101101";
var n = s.length;
document.write( minCuts(s, n));
</script>
Producción:
3
Complejidad temporal: O(n 2 )
Complejidad espacial: O(n)