Dada una string S compuesta por 0 y 1. Encuentre las divisiones mínimas tales que la substring sea una representación binaria de la potencia de 4 o 6 sin ceros a la izquierda. Imprima -1 si tal partición no es posible.
Ejemplos:
Input: 100110110 Output: 3 The string can be split into a minimum of three substrings 100(power of 4), 110 (power of 6) and 110(power of 6). Input : 00000 Output : -1 0 is not a power of 4 or 6.
Una solución simple es dividir la string recursivamente en diferentes índices y verificar si cada división es una potencia de 4 o 6. Comience con el índice 0 y divida str[0] de otra string. Si es una potencia de 4 o 6, llame recursivamente al índice 1 y realice la misma operación. Cuando se divide una string completa, compruebe si el número total de particiones es mínimo hasta el momento o no. Luego divida str[0..1], verifique si es la potencia de 4 o 6 y luego llame recursivamente para la string de descanso. Compare las particiones con el mínimo hasta ahora al final del recorrido de strings. Este enfoque será exponencial en el tiempo.
Una solución eficiente es usar Programación Dinámica. Se crea una tabla dp 1-D en la que dp[i] almacena el número mínimo de particiones requeridas para dividir la string str[i..n-1] en substrings que son potencias de 4 o 6. Supongamos que estamos en el índice i y str [i..j] es una potencia de 4 o 6, entonces el número mínimo de particiones será el número mínimo de particiones para dividir str[j+1..n-1] más una partición para dividir str[i..j] de string, es decir, dp[j+1] + 1. Por lo tanto, la relación de recurrencia para (j!=(n-1)) y (dp[j + 1]!=-1) será:
dp[i] = min(dp[i], dp[j + 1] + 1)
Implementación:
C++
// CPP program for Minimum splits in a
//string such that substring is a power of 4 or 6.
#include <bits/stdc++.h>
using namespace std;
// Function to find if given number
// is power of another number or not.
bool isPowerOf(long val, int base)
{
// Divide given number repeatedly
// by base value.
while (val > 1) {
if (val % base != 0)
return false; // not a power
val /= base;
}
return true;
}
// Function to find minimum number of
// partitions of given binary string
// so that each partition is power of 4 or 6.
int numberOfPartitions(string binaryNo)
{
int i, j, n = binaryNo.length();
// Variable to store integer value of
// given binary string partition.
long val;
// DP table to store results of
// partitioning done at differentindices.
int dp[n];
// If the last digit is 1, hence 4^0=1 and 6^0=1
dp[n - 1] = ((binaryNo[n - 1] - '0') == 0) ? -1 : 1;
// Fix starting position for partition
for (i = n - 2; i >= 0; i--) {
val = 0;
// Binary representation
// with leading zeroes is not allowed.
if ((binaryNo[i] - '0') == 0) {
dp[i] = -1;
continue;
}
dp[i] = INT_MAX;
// Iterate for all different partitions starting from i
for (j = i; j < n; j++) {
// Find integer value of current
// binary partition.
val = (val * 2) + (long)(binaryNo[j] - '0');
// Check if the value is a power of 4 or 6 or not
// apply recurrence relation
if (isPowerOf(val, 4) || isPowerOf(val, 6)) {
if (j == n - 1) {
dp[i] = 1;
}
else {
if (dp[j + 1] != -1)
dp[i] = min(dp[i], dp[j + 1] + 1);
}
}
}
// If no partitions are possible, then
// make dp[i] = -1 to represent this.
if (dp[i] == INT_MAX)
dp[i] = -1;
}
return dp[0];
}
// Driver code
int main()
{
string binaryNo = "100110110";
cout << numberOfPartitions(binaryNo);
return 0;
}
Java
// Java program for Minimum splits
// in a string such that substring
// is a power of 4 or 6.
import java.io.*;
class GFG
{
static boolean isPowerOf(long val,
int base)
{
// Divide given number
// repeatedly by base value.
while (val > 1)
{
if (val % base != 0)
return false; // not a power
val /= base;
}
return true;
}
// Function to find minimum
// number of partitions of
// given binary string so that
// each partition is power
// of 4 or 6.
static int numberOfPartitions(String binaryNo)
{
int i, j, n = binaryNo.length();
// Variable to store integer
// value of given binary
// string partition.
long val;
// DP table to store results
// of partitioning done at
// differentindices.
int dp[] = new int[n];
// If the last digit is 1,
// hence 4^0=1 and 6^0=1
dp[n - 1] = (((binaryNo.charAt(n - 1) -
'0') == 0) ?
-1 : 1);
// Fix starting position
// for partition
for (i = n - 2; i >= 0; i--)
{
val = 0;
// Binary representation
// with leading zeroes
// is not allowed.
if ((binaryNo.charAt(i) - '0') == 0)
{
dp[i] = -1;
continue;
}
dp[i] = Integer.MAX_VALUE;
// Iterate for all different
// partitions starting from i
for (j = i; j < n; j++)
{
// Find integer value of
// current binary partition.
val = (val * 2) +
(long)(binaryNo.charAt(j) - '0');
// Check if the value is a
// power of 4 or 6 or not
// apply recurrence relation
if (isPowerOf(val, 4) ||
isPowerOf(val, 6))
{
if (j == n - 1)
{
dp[i] = 1;
}
else
{
if (dp[j + 1] != -1)
dp[i] = Math.min(dp[i],
dp[j + 1] + 1);
}
}
}
// If no partitions are possible,
// then make dp[i] = -1 to
// represent this.
if (dp[i] == Integer.MAX_VALUE)
dp[i] = -1;
}
return dp[0];
}
// Driver code
public static void main (String[] args)
{
String binaryNo = "100110110";
System.out.println(numberOfPartitions(binaryNo));
}
}
// This code is contributed
// by shiv_bhakt.
Python 3
# Python 3 program for Minimum
# splits in a string such that
# substring is a power of 4 or 6.
import sys
# Function to find if given number
# is power of another number or not.
def isPowerOf(val, base):
# Divide given number repeatedly
# by base value.
while (val > 1):
if (val % base != 0):
return False # not a power
val //= base
return True
# Function to find minimum number of
# partitions of given binary string
# so that each partition is power of 4 or 6.
def numberOfPartitions(binaryNo):
n = len(binaryNo)
# DP table to store results of
# partitioning done at differentindices.
dp = [0] * n
# If the last digit is 1, hence 4^0=1 and 6^0=1
if ((ord(binaryNo[n - 1]) - ord('0')) == 0) :
dp[n - 1] = -1
else:
dp[n - 1] = 1
# Fix starting position for partition
for i in range( n - 2, -1, -1):
val = 0
# Binary representation
# with leading zeroes is not allowed.
if ((ord(binaryNo[i]) - ord('0')) == 0):
dp[i] = -1
continue
dp[i] = sys.maxsize
# Iterate for all different partitions starting from i
for j in range(i, n):
# Find integer value of current
# binary partition.
val = (val * 2) + (ord(binaryNo[j]) - ord('0'))
# Check if the value is a power of 4 or 6 or not
# apply recurrence relation
if (isPowerOf(val, 4) or isPowerOf(val, 6)):
if (j == n - 1):
dp[i] = 1
else :
if (dp[j + 1] != -1):
dp[i] = min(dp[i], dp[j + 1] + 1)
# If no partitions are possible, then
# make dp[i] = -1 to represent this.
if (dp[i] == sys.maxsize):
dp[i] = -1
return dp[0]
# Driver code
if __name__ == "__main__":
binaryNo = "100110110"
print(numberOfPartitions(binaryNo))
# This code is contributed by Ita_c.
C#
// C# program for Minimum splits
// in a string such that substring
// is a power of 4 or 6.
using System;
class GFG
{
static bool isPowerOf(long val, int b)
{
// Divide given number
// repeatedly by base value.
while (val > 1)
{
if (val % b != 0)
return false; // not a power
val /= b;
}
return true;
}
// Function to find minimum
// number of partitions of
// given binary string so that
// each partition is power
// of 4 or 6.
static int numberOfPartitions(string binaryNo)
{
int i, j, n = binaryNo.Length;
// Variable to store integer
// value of given binary
// string partition.
long val;
// DP table to store results
// of partitioning done at
// differentindices.
int[] dp = new int[n];
// If the last digit is 1,
// hence 4^0=1 and 6^0=1
dp[n - 1] = (((binaryNo[n - 1] -
'0') == 0) ?
-1 : 1);
// Fix starting position
// for partition
for (i = n - 2; i >= 0; i--)
{
val = 0;
// Binary representation
// with leading zeroes
// is not allowed.
if ((binaryNo[i] - '0') == 0)
{
dp[i] = -1;
continue;
}
dp[i] = int.MaxValue;
// Iterate for all different
// partitions starting from i
for (j = i; j < n; j++)
{
// Find integer value of
// current binary partition.
val = (val * 2) +
(long)(binaryNo[j] - '0');
// Check if the value is a
// power of 4 or 6 or not
// apply recurrence relation
if (isPowerOf(val, 4) ||
isPowerOf(val, 6))
{
if (j == n - 1)
{
dp[i] = 1;
}
else
{
if (dp[j + 1] != -1)
dp[i] = Math.Min(dp[i],
dp[j + 1] + 1);
}
}
}
// If no partitions are possible,
// then make dp[i] = -1 to
// represent this.
if (dp[i] == int.MaxValue)
dp[i] = -1;
}
return dp[0];
}
// Driver code
public static void Main ()
{
string binaryNo = "100110110";
Console.Write(numberOfPartitions(binaryNo));
}
}
Javascript
<script>
// Javascript program for Minimum splits in a
//string such that substring is a power of 4 or 6.
// Function to find if given number
// is power of another number or not.
function isPowerOf(val, base)
{
// Divide given number repeatedly
// by base value.
while (val > 1) {
if (val % base != 0)
return false; // not a power
val /= base;
}
return true;
}
// Function to find minimum number of
// partitions of given binary string
// so that each partition is power of 4 or 6.
function numberOfPartitions(binaryNo)
{
var i, j, n = binaryNo.length;
// Variable to store integer value of
// given binary string partition.
var val;
// DP table to store results of
// partitioning done at differentindices.
var dp = Array(n);
// If the last digit is 1, hence 4^0=1 and 6^0=1
dp[n - 1] = ((binaryNo[n - 1] - '0') == 0) ? -1 : 1;
// Fix starting position for partition
for (i = n - 2; i >= 0; i--) {
val = 0;
// Binary representation
// with leading zeroes is not allowed.
if ((binaryNo[i] - '0') == 0) {
dp[i] = -1;
continue;
}
dp[i] = 1000000000;
// Iterate for all different partitions starting from i
for (j = i; j < n; j++) {
// Find integer value of current
// binary partition.
val = (val * 2) + (binaryNo[j] - '0');
// Check if the value is a power of 4 or 6 or not
// apply recurrence relation
if (isPowerOf(val, 4) || isPowerOf(val, 6)) {
if (j == n - 1) {
dp[i] = 1;
}
else {
if (dp[j + 1] != -1)
dp[i] = Math.min(dp[i], dp[j + 1] + 1);
}
}
}
// If no partitions are possible, then
// make dp[i] = -1 to represent this.
if (dp[i] == 1000000000)
dp[i] = -1;
}
return dp[0];
}
// Driver code
var binaryNo = "100110110";
document.write( numberOfPartitions(binaryNo));
// This code is contributed by itsok.
</script>
Producción:
3
Complejidad de tiempo: O(n^2*log(x)), x = mayor potencia de 4 o 6 que se puede obtener de la string de entrada.
Espacio Auxiliar: O(n)