修改给定数组以使奇数和偶数索引元素的总和相同

2021年5月15日18:20:16 发表评论 1,003 次浏览

本文概述

给定一个大小为N的二进制数组arr[]，从数组中最多删除N/2个元素，使奇数和偶数下标的元素之和相等。任务是打印修改后的数组。

注意:N总是偶数。可能有多个结果，打印任何一个。

例子：

输入：arr [] = {1, 1, 1, 0}
输出：1 1
说明：对于给定的数组arr [] = {1, 1, 1, 0}在奇数位置的元素之和, Odd_Sum = arr [ 1] + arr [3] = 1 +1 =2。偶数位置的元素之和, Even_Sum = arr [2] + arr [4] = 1 + 0 =1。由于Odd_Sum和Even_Sum不相等, 因此删除一些使它们相等的元素。
删除arr [3]和arr [4]后, 数组变为arr [] = {1, 1}, 以使奇数索引和偶数索引处的元素之和相等。
输入：arr [] = {1, 0}
输出：0
说明：对于给定的数组arr [] = {1, 0}在奇数位置的元素之和, Odd_Sum = arr [1] = 0 = 0。偶数位置上的元素的平均, Even_Sum = 1 =1。由于Odd_Sum和Even_Sum不相等, 请删除一些元素以使其相等。删除arr [0]后, 数组变为arr [] = {0}, 以使奇数索引和偶数索引处的元素之和相等。

方法：这个想法是为了数数1s和0s在给定数组中, 然后通过以下步骤使结果总和相等：

  1. 数数0s和1s在给定的数组中arr []并将它们存储在变量中count_0和count_1分别。
  2. 如果在奇数和偶数索引处的元素之和相等, 则无需删除任何数组元素。打印原始数组作为答案。
  3. If计数_0≥N / 2, 然后删除所有1s并打印所有零count_0次数。
  4. 否则, 如果计数_0 <N / 2, 通过删除所有0s, 可以使偶数和奇数索引的总和与以下条件相同：
    • Ifcount_1是奇数, 然后打印1作为新数组的元素(计数_1 – 1)次数。
    • 否则, 打印1作为新数组的元素count_1次数。
  5. 根据上述条件打印结果数组。

下面是上述方法的实现：

C ++

//C++ program for the above approach
 
#include <bits/stdc++.h>
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++)
             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

输出如下：

1 1

时间复杂度：O(n)

辅助空间：O(1)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: