Longest substring of only 4 's from the first N characters of the infinite string | C ++ implementation of the approach ; Function to return the length of longest contiguous string containing only 4 aTMs from the first N characters of the string ; Initialize result ; Initialize prefix sum array of characters and product variable ; Preprocessing of prefix sum array ; Initialize variable to store the string length where N belongs to ; Finding the string length where N belongs to ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  30 NEW_LINE int countMaxLength ( int N ) { int res ; int pre [ MAXN ] , p = 1 ; pre [ 0 ] = 0 ; for ( int i = 1 ; i < MAXN ; i ++ ) { p *= 2 ; pre [ i ] = pre [ i - 1 ] + i * p ; } int ind ; 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 ; } int main ( ) { int N = 25 ; cout << countMaxLength ( N ) ; return 0 ; }