Given an integer N, the task is to find the length of the longest substring containing only 4’s from the first N characters of the infinite string str.
The string str is generated by concatenating the numbers formed by only 4’s and 5’s in increasing order. For example 4, 5, 44, 45, 54, 55 and so on. Therefore the string str looks like “4544455455444445454455…”.
Examples:
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.
Approach: The problem can be solved easily by observing the pattern. The task is to count the maximum consecutive 4’s appearing in the string. So, there is no need to generate the whole string.
We can observe a pattern if we divide the string into different groups as the first group will have 2 characters, the second group will have 4 characters, the third group will have 8 characters, and so on…
For Example:
Group 1 -> 45
Group 2 -> 44455455
Group 3 -> 444445454455544545554555
.
.
.
and, so on…
Now, the task reduces to finding the group in which N lies, and how many characters it covers in that group from start.
Here,
- If N falls in group 2, the answer will be at least 3. That is if, length = 4 then the answer will be 2 as with length 4, the string will cover only up to the 2nd 4 in the group, and if length = 5 answer will be 3.
- Similarly, if length covers at least the first 5 “4’s” from group 3, the answer is 5.
Now,
Group 1 has 1 * 2^1 characters
Group 2 has 2 * 2^2 characters
Generally, group K has K * 2^K characters. So the problem reduces to finding to which group, the given N belongs to. This can be easily found by using the prefix sum array pre[] where the ith element contains the sum of a number of characters up to the ith group.
Below is the implementation of the above approach:
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 stringint 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 Codeint main(){ int N = 25; cout << countMaxLength(N); return 0;} |
Java
// Java implementation of the approachclass 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 stringstatic 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 Codepublic 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 approachMAXN = 30# Function to return the length of longest# contiguous string containing only 4’s from# the first N characters of the stringdef 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 Codeif __name__ == '__main__': N = 25 print(countMaxLength(N))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing 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 stringstatic 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 Codepublic 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 approachvar MAXN = 30;// Function to return the length of longest// contiguous string containing only 4’s from// the first N characters of the stringfunction 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 Codevar N = 25;document.write(countMaxLength(N));// This code is contributed by noob2000</script> |
Output:
5
Time Complexity: O(MAXN)
Auxiliary Space: O(MAXN), where MAXN is a predefined value here. MAXN = 30
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
