Dado un número entero N, la tarea es encontrar la longitud de la substring más larga que contiene solo 4 de los primeros N caracteres de la string infinita str .
La string str se genera concatenando los números formados por solo 4 y 5 en orden creciente. Por ejemplo 4 , 5 , 44 , 45 , 54 , 55 y así sucesivamente. Por lo tanto, la string str parece «4544455455444445454455…» .
Ejemplos:
Input : N = 4 Output : 2 First 4 characters of str are "4544". Therefore the required length is 2. Input : N = 10 Output : 3 First 10 characters of str are "4544455455". Therefore the required length is 3.
Enfoque: El problema se puede resolver fácilmente observando el patrón. La tarea es contar el máximo de 4 consecutivos que aparecen en la string. Por lo tanto, no hay necesidad de generar la string completa.
Podemos observar un patrón si dividimos la string en diferentes grupos ya que el primer grupo tendrá 2 caracteres, el segundo grupo tendrá 4 caracteres, el tercer grupo tendrá 8 caracteres y así sucesivamente….
Por ejemplo :
Grupo 1 -> 4 5
Grupo 2 -> 444 55455
Grupo 3 -> 44444 5454455544545554555
.
.
.
y así…
Ahora, la tarea se reduce a encontrar el grupo en el que se encuentra N y cuántos caracteres cubre en ese grupo desde el principio.
Aquí,
- Si N cae en el grupo 2, la respuesta será al menos 3. Es decir, si longitud = 4, entonces la respuesta será 2 como con longitud 4, la string cubrirá solo hasta el segundo 4 en el grupo y si longitud = 5 la respuesta sera 3
- De manera similar, si la longitud cubre al menos los primeros 5 «4» del grupo 3, la respuesta es 5.
Ahora, el
Grupo 1 tiene 1 * 2 ^ 1 caracteres
. El Grupo 2 tiene 2 * 2 ^ 2 caracteres
. Generalmente, el grupo K tiene K * 2 ^ K caracteres. Así que el problema se reduce a encontrar a qué grupo pertenece el N dado. Esto se puede encontrar fácilmente usando la array de suma de prefijos pre[] donde el i-ésimo elemento contiene la suma del número de caracteres hasta el i-ésimo grupo.
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 MAXN 30
// Function to return the length of longest
// contiguous string containing only 4’s from
// the first N characters of the string
int countMaxLength(int N)
{
// Initialize result
int res;
// Initialize prefix sum array of
// characters and product variable
int pre[MAXN], p = 1;
// Preprocessing of prefix sum array
pre[0] = 0;
for (int i = 1; i < MAXN; i++) {
p *= 2;
pre[i] = pre[i - 1] + i * p;
}
// Initialize variable to store the
// string length where N belongs to
int ind;
// Finding the string length where
// N belongs to
for (int i = 1; i < MAXN; i++) {
if (pre[i] >= N) {
ind = i;
break;
}
}
int x = N - pre[ind - 1];
int y = 2 * ind - 1;
if (x >= y)
res = min(x, y);
else
res = max(x, 2 * (ind - 2) + 1);
return res;
}
// Driver Code
int main()
{
int N = 25;
cout << countMaxLength(N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAXN = 30;
// Function to return the length of longest
// contiguous string containing only 4's from
// the first N characters of the string
static int countMaxLength(int N)
{
// Initialize result
int res;
// Initialize prefix sum array of
// characters and product variable
int pre[] = new int[MAXN];
int p = 1;
// Preprocessing of prefix sum array
pre[0] = 0;
for (int i = 1; i < MAXN; i++)
{
p *= 2;
pre[i] = pre[i - 1] + i * p;
}
// Initialize variable to store the
// string length where N belongs to
int ind = 0;
// Finding the string length where
// N belongs to
for (int i = 1; i < MAXN; i++)
{
if (pre[i] >= N)
{
ind = i;
break;
}
}
int x = N - pre[ind - 1];
int y = 2 * ind - 1;
if (x >= y)
res = Math.min(x, y);
else
res = Math.max(x, 2 * (ind - 2) + 1);
return res;
}
// Driver Code
public static void main(String[] args)
{
int N = 25;
System.out.println(countMaxLength(N));
}
}
// This code is contributed by Code_Mech.
Python3
# Python 3 implementation of the approach MAXN = 30 # Function to return the length of longest # contiguous string containing only 4’s from # the first N characters of the string def countMaxLength(N): # Initialize result # Initialize prefix sum array of # characters and product variable pre = [0 for i in range(MAXN)] p = 1 # Preprocessing of prefix sum array pre[0] = 0 for i in range(1, MAXN, 1): p *= 2 pre[i] = pre[i - 1] + i * p # Initialize variable to store the # string length where N belongs to # Finding the string length where # N belongs to for i in range(1, MAXN, 1): if (pre[i] >= N): ind = i break x = N - pre[ind - 1] y = 2 * ind - 1 if (x >= y): res = min(x, y) else: res = max(x, 2 * (ind - 2) + 1) return res # Driver Code if __name__ == '__main__': N = 25 print(countMaxLength(N)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAXN = 30;
// Function to return the length of longest
// contiguous string containing only 4's from
// the first N characters of the string
static int countMaxLength(int N)
{
// Initialize result
int res;
// Initialize prefix sum array of
// characters and product variable
int[] pre = new int[MAXN];
int p = 1;
// Preprocessing of prefix sum array
pre[0] = 0;
for (int i = 1; i < MAXN; i++)
{
p *= 2;
pre[i] = pre[i - 1] + i * p;
}
// Initialize variable to store the
// string length where N belongs to
int ind = 0;
// Finding the string length where
// N belongs to
for (int i = 1; i < MAXN; i++)
{
if (pre[i] >= N)
{
ind = i;
break;
}
}
int x = N - pre[ind - 1];
int y = 2 * ind - 1;
if (x >= y)
res = Math.Min(x, y);
else
res = Math.Max(x, 2 * (ind - 2) + 1);
return res;
}
// Driver Code
public static void Main()
{
int N = 25;
Console.WriteLine(countMaxLength(N));
}
}
// This code is contributed by Code_Mech.
PHP
<?php
// PHP implementation of the approach
$MAXN = 30;
// Function to return the length of longest
// contiguous string containing only 4’s from
// the first N characters of the string
function countMaxLength($N)
{
// Initialize result
$res = 0;
// Initialize prefix sum array of
// characters and product variable
$pre = array();
$p = 1;
// Preprocessing of prefix sum array
$pre[0] = 0;
for ($i = 1; $i < $GLOBALS['MAXN']; $i++)
{
$p *= 2;
$pre[$i] = $pre[$i - 1] + $i * $p;
}
// Initialize variable to store the
// string length where N belongs to
$ind = 0;
// Finding the string length where
// N belongs to
for ($i = 1; $i < $GLOBALS['MAXN']; $i++)
{
if ($pre[$i] >= $N)
{
$ind = $i;
break;
}
}
$x = $N - $pre[$ind - 1];
$y = 2 * $ind - 1;
if ($x >= $y)
$res = min($x, $y);
else
$res = max($x, 2 * ($ind - 2) + 1);
return $res;
}
// Driver Code
$N = 25;
echo countMaxLength($N);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
var MAXN = 30;
// Function to return the length of longest
// contiguous string containing only 4’s from
// the first N characters of the string
function countMaxLength(N)
{
// Initialize result
var res;
// Initialize prefix sum array of
// characters and product variable
var pre = Array(MAXN), p = 1;
// Preprocessing of prefix sum array
pre[0] = 0;
for(var i = 1; i < MAXN; i++)
{
p *= 2;
pre[i] = pre[i - 1] + i * p;
}
// Initialize variable to store the
// string length where N belongs to
var ind;
// Finding the string length where
// N belongs to
for(var i = 1; i < MAXN; i++)
{
if (pre[i] >= N)
{
ind = i;
break;
}
}
var x = N - pre[ind - 1];
var y = 2 * ind - 1;
if (x >= y)
res = Math.min(x, y);
else
res = Math.max(x, 2 * (ind - 2) + 1);
return res;
}
// Driver Code
var N = 25;
document.write(countMaxLength(N));
// This code is contributed by noob2000
</script>
5
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA