Good XOR | codechef | starters 81

Problem

An binary array is called good, if the count of ones in the array is equal to the count of zeros.

Chef has a binary array �A of size �N. He wants to make the array good using the following type of operation:

  • Select two indices �i and �j (�≠�)(i=j) and set both ��Ai​ and ��Aj​ as ��⊕��Ai​⊕Aj​, where ⊕⊕ denotes the bitwise XOR operation.

Determine the minimum number of operations required to make the array good. If it is not possible to make the array good using any number of operations, print −1−1.

Input Format

  • The first line of input will contain a single integer �T, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains an integer �N, the size of the array.
    • The second line contains �N space-separated integers, denoting the array �A.

Output Format

For each test case, output on a new line, the minimum number of operations required to make the array good. If it is not possible to make the array good using any number of operations, print −1−1.

Constraints

  • 1≤�≤7001≤T≤700
  • 1≤�≤1051≤N≤105
  • 0≤��≤10≤Ai​≤1
  • The sum of �N over all test cases does not exceed 2⋅1052⋅105.

Sample 1:

Input

Output

3
1
0
2
1 0
4
1 0 0 0
-1
0
1

Explanation:

Test case 11: It is not possible to make the array good using any number of operations.

Test case 22: The number of ones as well as zeros is 11. Since the array is already good, we do not need to apply any operation.

Test case 33: The number of ones is 11 and the number of zeros is 33. We perform the following operation:

  • Select �=1i=1 and �=3j=3, and set �1A1​ and �3A3​ as �1⊕�3=1⊕0=1A1​⊕A3​=1⊕0=1. Thus, array becomes [1,0,1,0][1,0,1,0].

The array has equal number of zeros and ones now. Thus, the array is good.

click on below image to get the solution:

Leave a Reply

Your email address will not be published. Required fields are marked *

यकीन नहीं मानोगे! ये 9 जगहें हैं UP में जो ताजमहल को भी फीका कर देंगी! मेरठ: इतिहास, धर्म और खूबसूरती का संगम! घूमने के लिए ये हैं बेहतरीन जगहें रोज आंवला खाने के 10 धांसू फायदे जो आपको कर देंगे हेल्दी और फिट! Anjali Arora to play Maa Sita: रामायण फिल्म में सीता का रोल निभाएंगी अंजली अरोड़ा, तैयारियों में लगी? Rinku Singh : रिंकू सिंह ने अपने दाहिने हाथ पर बने टैटू का खोला राज, सुनकर हो जायेंगे दंग Panchayat Season 3 Release Date: फुलेरा में मचा भूचाल! क्या अभिषेक इस बार हार जाएगा?