Dada una array binaria arr[] de tamaño N , elimine como máximo N/2 elementos de la array de modo que la suma de los elementos en los índices pares e impares sea igual. La tarea es imprimir la array modificada.
Nota: N siempre es par. Puede haber más de un resultado posible, imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {1, 1, 1, 0}
Salida: 1 1
Explicación:
Para la array dada arr[] = {1, 1, 1, 0}
La suma de elementos en posición impar, Odd_Sum = arr[ 1] + arr[3] = 1 + 1 = 2.
La suma de los elementos en la posición par, Even_Sum = arr[2] + arr[4] = 1 + 0 = 1.
Dado que Odd_Sum y Even_Sum no son iguales, elimine algunos elementos para igualarlos.
Después de eliminar arr[3] y arr[4], la array se convierte en arr[] = {1, 1} tal que la suma de los elementos en los índices impares y los índices pares son iguales.Entrada: arr[] = {1, 0}
Salida: 0
Explicación:
Para la array dada arr[] = {1, 0}
La suma de elementos en posición impar, Odd_Sum = arr[1] = 0 = 0.
La suma de elementos en posición par, Even_Sum = 1 = 1.
Dado que Odd_Sum y Even_Sum no son iguales, elimine algunos elementos para hacerlos iguales.
Después de eliminar arr[0], la array se convierte en arr[] = {0} tal que la suma de los elementos en los índices impares y los índices pares son iguales.
Enfoque: la idea es contar el número de 1 y 0 en la array dada y luego igualar la suma resultante mediante los siguientes pasos:
- Cuente el número de 0s y 1s en la array dada arr[] y guárdelos en variables digamos count_0 y count_1 respectivamente.
- Si la suma de los elementos en los índices pares e impares es igual, entonces no es necesario eliminar ningún elemento de la array. Imprime la array original como la respuesta.
- Si count_0 ≥ N/2 , elimine todos los 1 e imprima todos los ceros count_0 varias veces.
- De lo contrario, si count_0 < N/2 , al eliminar todos los 0 , la suma de los índices pares e impares puede hacerse igual según las siguientes condiciones:
- Si count_1 es impar , imprima 1 como un elemento de la nueva array (count_1 – 1) varias veces.
- De lo contrario, imprima 1 como un elemento de la nueva array count_1 varias veces.
- Imprima la array resultante según las condiciones anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to modify array to make
// sum of odd and even indexed
// elements equal
void makeArraySumEqual(int a[], int N)
{
// Stores the count of 0s, 1s
int count_0 = 0, count_1 = 0;
// Stores sum of odd and even
// indexed elements respectively
int odd_sum = 0, even_sum = 0;
for (int i = 0; i < N; i++) {
// Count 0s
if (a[i] == 0)
count_0++;
// Count 1s
else
count_1++;
// Calculate odd_sum and even_sum
if ((i + 1) % 2 == 0)
even_sum += a[i];
else if ((i + 1) % 2 > 0)
odd_sum += a[i];
}
// If both are equal
if (odd_sum == even_sum) {
// Print the original array
for (int i = 0; i < N; i++)
cout <<" "<< a[i];
}
// Otherwise
else {
if (count_0 >= N / 2) {
// Print all the 0s
for (int i = 0; i < count_0; i++)
cout <<"0 ";
}
else {
// For checking even or odd
int is_Odd = count_1 % 2;
// Update total count of 1s
count_1 -= is_Odd;
// Print all 1s
for (int i = 0; i < count_1; i++)
cout <<"1 ";
}
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 1, 1, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
makeArraySumEqual(arr, N);
return 0;
}
// This code is contributed by shivanisinghss2110.
C
// C++ program for the above approach
#include <stdio.h>
// Function to modify array to make
// sum of odd and even indexed
// elements equal
void makeArraySumEqual(int a[], int N)
{
// Stores the count of 0s, 1s
int count_0 = 0, count_1 = 0;
// Stores sum of odd and even
// indexed elements respectively
int odd_sum = 0, even_sum = 0;
for (int i = 0; i < N; i++) {
// Count 0s
if (a[i] == 0)
count_0++;
// Count 1s
else
count_1++;
// Calculate odd_sum and even_sum
if ((i + 1) % 2 == 0)
even_sum += a[i];
else if ((i + 1) % 2 > 0)
odd_sum += a[i];
}
// If both are equal
if (odd_sum == even_sum) {
// Print the original array
for (int i = 0; i < N; i++)
printf("%d ", a[i]);
}
// Otherwise
else {
if (count_0 >= N / 2) {
// Print all the 0s
for (int i = 0; i < count_0; i++)
printf("0 ");
}
else {
// For checking even or odd
int is_Odd = count_1 % 2;
// Update total count of 1s
count_1 -= is_Odd;
// Print all 1s
for (int i = 0; i < count_1; i++)
printf("1 ");
}
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 1, 1, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
makeArraySumEqual(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG {
// Function to modify array to make
// sum of odd and even indexed
// elements equal
static void makeArraySumEqual(int a[], int N)
{
// Stores the count of 0s, 1s
int count_0 = 0, count_1 = 0;
// Stores sum of odd and even
// indexed elements respectively
int odd_sum = 0, even_sum = 0;
for (int i = 0; i < N; i++) {
// Count 0s
if (a[i] == 0)
count_0++;
// Count 1s
else
count_1++;
// Calculate odd_sum and even_sum
if ((i + 1) % 2 == 0)
even_sum += a[i];
else if ((i + 1) % 2 > 0)
odd_sum += a[i];
}
// If both are equal
if (odd_sum == even_sum) {
// Print the original array
for (int i = 0; i < N; i++)
System.out.print(a[i] + " ");
}
else
{
if (count_0 >= N / 2) {
// Print all the 0s
for (int i = 0; i < count_0; i++)
System.out.print("0 ");
}
else {
// For checking even or odd
int is_Odd = count_1 % 2;
// Update total count of 1s
count_1 -= is_Odd;
// Print all 1s
for (int i = 0; i < count_1; i++)
System.out.print("1 ");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 1, 1, 0 };
int N = arr.length;
// Function Call
makeArraySumEqual(arr, N);
}
}
Python3
# Python3 program for the above approach
# Function to modify array to make
# sum of odd and even indexed
# elements equal
def makeArraySumEqual(a, N):
# Stores the count of 0s, 1s
count_0 = 0
count_1 = 0
# Stores sum of odd and even
# indexed elements respectively
odd_sum = 0
even_sum = 0
for i in range(N):
# Count 0s
if (a[i] == 0):
count_0 += 1
# Count 1s
else:
count_1 += 1
# Calculate odd_sum and even_sum
if ((i + 1) % 2 == 0):
even_sum += a[i]
elif ((i + 1) % 2 > 0):
odd_sum += a[i]
# If both are equal
if (odd_sum == even_sum):
# Print the original array
for i in range(N):
print(a[i], end = " ")
# Otherwise
else:
if (count_0 >= N / 2):
# Print all the 0s
for i in range(count_0):
print("0", end = " ")
else:
# For checking even or odd
is_Odd = count_1 % 2
# Update total count of 1s
count_1 -= is_Odd
# Print all 1s
for i in range(count_1):
print("1", end = " ")
# Driver Code
# Given array arr[]
arr = [ 1, 1, 1, 0 ]
N = len(arr)
# Function call
makeArraySumEqual(arr, N)
# This code is contributed by code_hunt
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to modify array to make
// sum of odd and even indexed
// elements equal
static void makeArraySumEqual(int []a,
int N)
{
// Stores the count of 0s, 1s
int count_0 = 0, count_1 = 0;
// Stores sum of odd and even
// indexed elements respectively
int odd_sum = 0, even_sum = 0;
for (int i = 0; i < N; i++)
{
// Count 0s
if (a[i] == 0)
count_0++;
// Count 1s
else
count_1++;
// Calculate odd_sum and even_sum
if ((i + 1) % 2 == 0)
even_sum += a[i];
else if ((i + 1) % 2 > 0)
odd_sum += a[i];
}
// If both are equal
if (odd_sum == even_sum)
{
// Print the original array
for (int i = 0; i < N; i++)
Console.Write(a[i] + " ");
}
else
{
if (count_0 >= N / 2)
{
// Print all the 0s
for (int i = 0; i < count_0; i++)
Console.Write("0 ");
}
else
{
// For checking even or odd
int is_Odd = count_1 % 2;
// Update total count of 1s
count_1 -= is_Odd;
// Print all 1s
for (int i = 0; i < count_1; i++)
Console.Write("1 ");
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 1, 1, 0};
int N = arr.Length;
// Function Call
makeArraySumEqual(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to modify array to make
// sum of odd and even indexed
// elements equal
function makeArraySumEqual(a, N)
{
// Stores the count of 0s, 1s
let count_0 = 0, count_1 = 0;
// Stores sum of odd and even
// indexed elements respectively
let odd_sum = 0, even_sum = 0;
for (let i = 0; i < N; i++) {
// Count 0s
if (a[i] == 0)
count_0++;
// Count 1s
else
count_1++;
// Calculate odd_sum and even_sum
if ((i + 1) % 2 == 0)
even_sum += a[i];
else if ((i + 1) % 2 > 0)
odd_sum += a[i];
}
// If both are equal
if (odd_sum == even_sum) {
// Print the original array
for (let i = 0; i < N; i++)
document.write(a[i] + " ");
}
else
{
if (count_0 >= N / 2) {
// Print all the 0s
for (let i = 0; i < count_0; i++)
document.write("0 ");
}
else {
// For checking even or odd
let is_Odd = count_1 % 2;
// Update total count of 1s
count_1 -= is_Odd;
// Print all 1s
for (let i = 0; i < count_1; i++)
document.write("1 ");
}
}
}
// Driver Code
// Given array arr[]
let arr = [ 1, 1, 1, 0 ];
let N = arr.length;
// Function Call
makeArraySumEqual(arr, N);
</script>
Producción:
1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aimformohan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA