make the array even?

user_14109531 0
Viewed 256

You are given an array A of N integers. If you make the array whole using the following operation, then what is the minimum number of operations required to make the entire array even?

Note : It can be proved that this is always possible.

Operation

Select an index

and perform operation:

P=A[i]+A[i+1]; Q=A[i]-A[i+1];

A[i]=P; A[i+1]=Q;

link to whole question

this is my code

for i in range(int(input())):
    N=int(input())
    arr=list(map(int,input().split()))
    dic=[i for i in range(N) if arr[i]%2!=0 ]
    value=0
    for i in range(len(dic)-1):
        k=dic[i+1]-dic[i]
        value+=k
    print(value)

testcases.............

testcase1:
         N=6
         arr= 1 6 4 3 4 2
         my output = 3
         expected output = 4

i do not get how come four operations is need in this testcase were as it only need three operation .

  testcase 2:
           N=6
           arr = 1 6 4 3 5 2
           my output = 4
           expected output =3

in this testcase all the integers will not be converted into even number no matter how many operations we applied .

if someone could show me how come testcase2 is done in three operation .

testcase1 will be done in four operation .

and were i am doing it wrong

can it be solved with bit manipulation.

bit-manipulation python-3.x python
2 Answers

Here is a code you can try for your problem.

def countOperations(arr, n) :
 
    count = 0;
 
    # Traverse the given array
    for i in range(n - 1) :
 
        # If an odd element occurs
        # then increment that element
        # and next adjacent element
        # by 1
        if (arr[i] & 1) :
            arr[i] += 1;
            arr[i + 1] += 1;
            count += 2;
 
    # Traverse the array if any odd
    # element occurs then return -1
    for i in range(n) :
        if (arr[i] & 1) :
            return -1;
 
    # Returns the count of operations
    return count;
 
if __name__ == "__main__" :
 
    arr = [ 2, 3, 4, 5, 6 ];
    n = len(arr);
    print(countOperations(arr, n));
user_157467620

in this testcase all the integers will not be converted into even number no matter how many operations we applied .

  • Yes they can be. See my below solution.

The idea is simple. I haven't used any bit manipulation, but here is how I would do it ,

  • odd +/- odd = even
  • odd +/- even = odd

For an i, if A[i] is even, I wouldnt care. Consider all i, such that A[i] is odd.

  • If A[i+1] is odd, I have P= odd+odd and Q=odd-odd, both even in one operation. I'll increase count by 1.
  • If A[i+1] is even, I have P=odd+even and Q= odd-even, both odd. I have done one operation. Now, I have two odds, one more operation and I can make both even. So, I'll increase count by 2.

if someone could show me how come testcase2 is done in three operation .

  • Operation 1 : [1 6 4 3 5 2] -> [7 -5 4 3 5 2] , A[0] = A[0] + A[1], A[1] = A[0] - A[1]
  • Operation 2 : [7 -5 4 3 5 2] -> [2 12 4 3 5 2], A[0] = A[0] + A[1], A[1] = A[0] - A[1]
  • Operation 3 : [2 12 4 3 5 2] -> [2 12 4 8 -2 2], A[3] = A[3] + A[4], A[4] = A[3] - A[4]

can it be solved with bit manipulation.

Here is a possible implementation :

def count_ops(A,n):
    count = 0 
    i = 0 
    done_last = False
    while(i < n-1):
        if(A[i]%2 == 0):
            i+=1
            continue
        if(i == n-2):
            done_last = True
        if(A[i+1]%2 == 0):
            count += 2
        else:
            count += 1
        i += 2
    if(not done_last):
        if(A[n-1]%2 == 1):
            count += 2
    print(count)
    return count

Notice the done_last flag, I'll leave it up to you to figure out.

user_120759970
Related