Longest substring of only 4 's from the first N characters of the infinite string | Java implementation of the approach ; Function to return the length of longest contiguous string containing only 4 's 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
class GFG { static int MAXN = 30 ; static int countMaxLength ( int N ) { int res ; int pre [ ] = new int [ MAXN ] ; int p = 1 ; pre [ 0 ] = 0 ; for ( int i = 1 ; i < MAXN ; i ++ ) { p *= 2 ; pre [ i ] = pre [ i - 1 ] + i * p ; } int ind = 0 ; 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 ; } public static void main ( String [ ] args ) { int N = 25 ; System . out . println ( countMaxLength ( N ) ) ; } }