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:
- Elimine cualquier par de elementos de la array e inserte su suma en una array.
- 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 igualesEntrada: 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++
// 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
// 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
# 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#
// 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
Javascript
<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.