Dado un número entero N (2 ≤ N ≤ 1e6) , la tarea es encontrar el máximo elemento presente en el arreglo arr[] de tamaño N + 1 generado en base a los siguientes pasos:
- array[0] = 0
- array[1] = 1
- arr[2 * i] = arr[i], cuando 2 ≤ 2 * i ≤ N
- arr[2 * i + 1] = Arr[i] + Arr[i + 1] cuando 2 ≤ 2 * i + 1 ≤ N
Ejemplos:
Entrada: N = 7
Salida: 3
Explicación: Construcción de la array basada en las reglas dadas:
- 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
Por lo tanto, la array construida es {0, 1, 1, 2, 1, 3, 2, 3}. El elemento máximo presente en la array es 3.
Entrada: N = 2
Salida: 1
Explicación: Según las reglas dadas, el máximo entre Arr[0], Arr[1] y Arr[2] es 1.
Enfoque: Para resolver el problema, la idea es generar todos los elementos de la array en función del conjunto de reglas dado y luego encontrar el máximo entre ellos. Encuentre cada elemento de la array de forma iterativa siguiendo los siguientes pasos:
Si i es par: Arr[i] = Arr[i/2]
De lo contrario, si i es impar: Arr[i] = Arr[(i – 1)/2] + Arr[(i – 1)/2 +1 ]
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA