Maximice el conteo de números iguales en la array de números hasta N reemplazando pares con su suma

Dada una array arr[] que contiene números naturales del 1 al N , la tarea es encontrar el número máximo de elementos que se pueden igualar después de las siguientes operaciones:

1. Elimine cualquier par de elementos de la array e inserte su suma en una array.
2. Repita la operación anterior cualquier número de veces para maximizar el recuento de elementos iguales.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4} 
Salida: 2 
Explicación: 
Podemos realizar las siguientes operaciones: 
{1, 2, 3, 4} -> {3, 3, 4} -> 2 elementos son iguales

Entrada: arr[] = {1 2 3 4 5 6} 
Salida: 3 
Explicación: 
{1, 2, 3, 4, 5, 6} -> {7, 2, 3, 4, 5} -> {7, 7, 3, 4} -> {7, 7, 37} -> 3 elementos son iguales

Enfoque: La observación clave en el problema es que:

• Si N es par , podemos hacer un recuento máximo de elementos iguales por

• Si N es impar , podemos hacer el conteo máximo de elementos iguales por

Por lo tanto, la respuesta siempre será 

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count maximum number
// of array elements equal
int countEqual(int n)
{
    return (n + 1) / 2;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << countEqual(n);
    return 0;
}

// Java implementation of
// the above approach
import java.io.*;
 
class GFG{
 
// Function to count maximum number
// of array elements equal
static int countEqual(int n)
{
    return (n + 1) / 2;
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    int n = arr.length;
 
    // Function call
    System.out.println(countEqual(n));
}
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of
# the above approach
 
# Function to count maximum number
# of array elements equal
def countEqual(n):
 
    return (n + 1) // 2
 
# Driver Code
lst = [ 1, 2, 3, 4, 5, 6 ]
n = len(lst)
 
# Function call
print(countEqual(n))
 
# This code is contributed by vishu2908

// C# implementation of
// the above approach
using System;
class GFG{
 
// Function to count maximum number
// of array elements equal
static int countEqual(int n)
{
    return (n + 1) / 2;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = {1, 2, 3, 4, 5, 6};
    int n = arr.Length;
 
    // Function call
    Console.WriteLine(countEqual(n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript implementation of
// the above approach
 
// Function to count maximum number
// of array elements equal
function countEqual(n)
{
    return parseInt((n + 1) / 2);
}
 
// Driver Code
var arr = [ 1, 2, 3, 4, 5, 6 ];
var n = arr.length;
 
// Function Call
document.write( countEqual(n));
 
// This code is contributed by rrrtnx.
</script>

3

Análisis de rendimiento:

Complejidad de tiempo : O(1), ya que no estamos usando bucles ni recursividad.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.