L56game - editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Kirill Gulin
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an array of N integers, you have to minimize the number of integers in final array after performing the following operation any number of times (including zero).

Select any two integers, such that their sum is even, remove both of them from array and insert their sum into array.

QUICK EXPLANATION

  • Minimum number of elements in final array will always be 1 or 2.
  • Sum of two numbers of same parity is even.
  •   Which means that our operation will always be applied on two odd or two even numbers, but never on one odd and one even number.
  • This problem can be solved even using two booleans, without storing the elements, though it isn’t necessary to solve the problem. Frequency of odd and even number serve the purpose.

EXPLANATION

Few observations

  •   Operation can only be applied on elements with same parity because sum of two number with different parity is always odd, thus, not allowed by our operation.

  • Minimum number of elements in final array will always be 1 or 2.
    Proof:
    Suppose our final array contains more than two, say 3 elements. Then, either the frequency of either odd or even elements will be greater than one, Thus, allowing us to perform one more operation, thereby reducing the size of final array to 2.

    Size of final array will be 1, if given array contains even number of odd elements, thus no odd number in final array.

For all even numbers, we can just merge them all into a single number. If there are M odd numbers in given array, we can merge floor(M/2) pair of odd numbers, resulting in one even number and one odd number (only if M is odd).

Thus, there will be one odd number (if frequency of odd numbers in array is odd), and/or one even number (if given array has at least one even number or at least two odd numbers).

We can separately determine if the final array will contain odd element and/or even element and output accordingly.

Complexity:
Time Complexity is O(N). Space Complexity is O(1).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution will be uploaded soon
Tester’s solution
Editorialist’s solution

2 Likes
2

There was a corner case in this problem which did not appear in the test cases. Most of the submissions(including mine) would give wrong answer.
The test case is :
1
1
1
The answer should be 1, but my submission would give answer as 2.
Weak test cases yet again. I would suggest admin to rejudge the submissions.

4 Likes
3

The correct answer for your test case is 2, not 1.

1 Like
4

I’m sorry, I didn’t understand. Can you please make it clear. If n = 1 and the given number is odd, no operation can be performed. So answer should be 1. I think you misunderstood the test case

1 Like
5

@taran_1407 - he is giving the TC in format

T N A[i] , so its T=1, N=1, arr[i]=1. I think he has a point.

1 Like
6

SOLUTION:-

ODD+ODD=EVEN

ODD+EVEN=ODD

EVEN+ODD=ODD

EVEN+EVEN=EVEN

So if there are Odd number of odds, there will be one odd left and there will be two elements else everything can be made even and only one element will remain.

for _ in range(int(input())):
  n=input()
  n=int((n))
  a=list(map(int,input().split()))
  arr=[0,0]
  even=0
  for i in range(n):
     if(a[i]&1):
       arr[0]+=1
     else:
       arr[1]+=1
   even+=arr[0]//2+arr[1]
   ans=arr[0]%2+min(even,1)
   print(ans)

PLEASE VISIT THIS LINK TO DOWNLOAD FILE:-FILE

2 Likes
7

Tester missed the corner case …when n=1,answer should be 1.

8

i need help with my logic : if (odd_count & 1) ans=2 , else ans=1. Can someone give an example where this logic fails ?

9

Here-

 1
1
1

T=1, N=1, arr[0]=1. You will print 2 for this.

10

Is that the only case where it fails ?

11

Yes, I believe this is the only failing TC for your solution.

You need to check if final array contains an odd element, an even element or both.

Array will contain both odd and even, only when odd_count&1 == 1 AND (even >0 OR odd > 1). In all other cases, ans is one.

12

Why dont you try and see? :confused: Saying because it often happens that you fix a case and another breaks down. :slight_smile:

1 Like