Find the largest element in an array generated using the given conditions
Given an integer N (2 ? N ? 1e6), the task is to find the maximum element present in the array arr[] of size N + 1 generated based on the following steps:
- arr[0] = 0
- arr[1] = 1
- arr[2 * i] = arr[i], when 2 ? 2 * i ? N
- arr[2 * i + 1] = Arr[i] + Arr[i + 1] when 2 ? 2 * i + 1 ? N
Examples:
Input: N = 7
Output: 3
Explanation: Constructing the array based on the given rules:
- Arr[0] = 0
- Arr[1] = 1
- Arr[(1 * 2) = 2] = Arr[1] = 1
- Arr[(1 * 2) + 1 = 3] = Arr[1] + Arr[2] = 1 + 1 = 2
- Arr[(2 * 2) = 4] = Arr[2] = 1
- Arr[(2 * 2) + 1 = 5] = Arr[2] + Arr[3] = 1 + 2 = 3
- Arr[(3 * 2) = 6] = Arr[3] = 2
- Arr[(3 * 2) + 1 = 7] = Arr[3] + Arr[4] = 2 + 1 = 3
Therefore, the array constructed is {0, 1, 1, 2, 1, 3, 2, 3}. The maximum element present in the array is 3.
Input: N = 2
Output: 1
Explanation: According to the given rules, the maximum among Arr[0], Arr[1], and Arr[2] is 1.
Approach: To solve the problem, the idea is to generate all the array elements based on the given set of rules and then, find the maximum among them. Find every array element iteratively using the following steps:
If i is even: Arr[i] = Arr[i/2]
Otherwise, if i is odd: Arr[i] = Arr[(i – 1)/2] + Arr[(i – 1)/2 +1]
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to generate the // required array vector< int > findArray( int n) { // Stores the array vector< int > Arr(n + 1); // Base case Arr[0] = 0; Arr[1] = 1; // Iterate over the indices for ( int i = 2; i <= n; i++) { // If current index is even if (i % 2 == 0) { Arr[i] = Arr[i / 2]; } // Otherwise else { Arr[i] = Arr[(i - 1) / 2] + Arr[(i - 1) / 2 + 1]; } } return Arr; } // Function to find and return // the maximum array element int maxElement( int n) { // If n is 0 if (n == 0) return 0; // If n is 1 if (n == 1) return 1; // Generates the required array vector< int > Arr = findArray(n); // Return maximum element of Arr return *max_element( Arr.begin(), Arr.end()); } // Driver Code int main() { int N = 7; cout << maxElement(N); return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; import java.util.Arrays; class GFG{ // Function to generate the // required array and to find // and return the maximum array // element static int [] findArray( int n) { // Stores the array int Arr[] = new int [n + 1 ]; // Base case Arr[ 0 ] = 0 ; Arr[ 1 ] = 1 ; // Iterate over the indices for ( int i = 2 ; i <= n; i++) { // If current index is even if (i % 2 == 0 ) { Arr[i] = Arr[i / 2 ]; } // Otherwise else { Arr[i] = Arr[(i - 1 ) / 2 ] + Arr[(i - 1 ) / 2 + 1 ]; } } return Arr; } // Function to find and return // the maximum array element static int maxElement( int n) { // If n is 0 if (n == 0 ) return 0 ; // If n is 1 if (n == 1 ) return 1 ; // Generates the required array int [] Arr = findArray(n); // Return maximum element of Arr int ans = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { ans = Math.max(ans, Arr[i]); } return ans; } // Driver Code public static void main(String args[]) { int N = 7 ; System.out.println(maxElement(N)); } } // This code is contributed by ananyadixit8 |
Python3
# Python3 program to implement # the above approach # Function to generate the # required array def findArray(n): # Stores the array Arr = [ 0 ] * (n + 1 ) # Base case Arr[ 1 ] = 1 # Iterate over the indices for i in range ( 2 , n + 1 ): # If current index is even if (i % 2 = = 0 ): Arr[i] = Arr[i / / 2 ] # Otherwise else : Arr[i] = (Arr[(i - 1 ) / / 2 ] + Arr[(i - 1 ) / / 2 + 1 ]) return Arr # Function to find and return # the maximum array element def maxElement(n): # If n is 0 if (n = = 0 ): return 0 # If n is 1 if (n = = 1 ): return 1 # Generates the required array Arr = findArray(n) # Return maximum element of Arr return max (Arr) # Driver Code if __name__ = = "__main__" : N = 7 print (maxElement(N)) # This code is contributed by AnkThon |
C#
// C# program to implement // the above approach using System; class GFG { // Function to generate the // required array and to find // and return the maximum array // element static int [] findArray( int n) { // Stores the array int []Arr = new int [n + 1]; // Base case Arr[0] = 0; Arr[1] = 1; // Iterate over the indices for ( int i = 2; i <= n; i++) { // If current index is even if (i % 2 == 0) { Arr[i] = Arr[i / 2]; } // Otherwise else { Arr[i] = Arr[(i - 1) / 2] + Arr[(i - 1) / 2 + 1]; } } return Arr; } // Function to find and return // the maximum array element static int maxElement( int n) { // If n is 0 if (n == 0) return 0; // If n is 1 if (n == 1) return 1; // Generates the required array int [] Arr = findArray(n); // Return maximum element of Arr int ans = int .MinValue; for ( int i = 0; i < n; i++) { ans = Math.Max(ans, Arr[i]); } return ans; } // Driver Code public static void Main(String []args) { int N = 7; Console.WriteLine(maxElement(N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to generate the // required array and to find // and return the maximum array // element function findArray(n) { // Stores the array let Arr = Array.from({length: n+1}, (_, i) => 0); // Base case Arr[0] = 0; Arr[1] = 1; // Iterate over the indices for (let i = 2; i <= n; i++) { // If current index is even if (i % 2 == 0) { Arr[i] = Arr[i / 2]; } // Otherwise else { Arr[i] = Arr[(i - 1) / 2] + Arr[(i - 1) / 2 + 1]; } } return Arr; } // Function to find and return // the maximum array element function maxElement(n) { // If n is 0 if (n == 0) return 0; // If n is 1 if (n == 1) return 1; // Generates the required array let Arr = findArray(n); // Return maximum element of Arr let ans = Number.MIN_VALUE; for (let i = 0; i < n; i++) { ans = Math.max(ans, Arr[i]); } return ans; } // Driver Code let N = 7; document.write(maxElement(N)); // This code is contributed by souravghosh0416. </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)