### PROBLEM LINK:

Author: Ankit Srivastava and Uttam Kanodia

Tester: Roman Rubanenko

Editorialist: Amit Pandey

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

Basic programming

### PROBLEM:

Given an array of n integers, you have to do the following operation K times: Insert a number in the array which is strictly greater than current sum of the array. You have to find whether the last number inserted is even or odd.

### QUICK EXPLANATION:

As the value of K is small, we can keep inserting smallest possible numbers at each step and print the K^{th} number modulo 2.

### EXPLANATION:

This problem can be solved by simulating the operation given in the problem.

First find the sum of the given array(A) . This can be done in O(N) time using a single loop. As we have to print the K^{th} element to be inserted (modulo 2), we can replace S by S\ \% \ 2.

S = 0; for(int i=0; i< n; i++) S = S + A[i]; S = S%2;

Now make an array B of size (K+1), B_i will denote the i^{th} element to be inserted, and B_K will be our required answer. At any step, if parity of the sum of the elements of array is â€śevenâ€ť, parity of inserted element will be â€śoddâ€ť.

B[1] = (S + 1) % 2 ; // we will insert the smallest possible number at each step total_sum = 0; for(int i=2 ; i< K ; i++) { total_sum = (total_sum + B[i-1]); B[i] = (total_sum + 1) % 2; // insert a number greater than current sum of the array. }

Finally we can output B_K. The time complexity of the whole code will be \mathcal{O}(N + K).

**Another solution**

Let us say that sum of the array A is even. The next inserted element will be odd, now sum of array will be odd, so next inserted element will be even, now sum of array becomes odd, so we will insert an even number, and so on. So we can generalize that if sum of array is even, then for K = 1, last inserted number will be odd, otherwise it will be even.

Now, we will consider the case in which sum of the array A is odd. The next inserted element will be even, now sum of array will become odd, so next inserted element will be even, now sum of array will be odd, we will add another even number, and so on. So we can generalize that last inserted number is always even in this case.

So finally, we can obtain the following simple solution.

Compute sum of array. If K = 1: if sum is even: print "odd" else: print "even" else: print "even"

### Solution:

Setterâ€™s solution can be found here

Testerâ€™s solution can be found here