PROBLEM LINK:Author: Ankit Srivastava and Uttam Kanodia 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[i1]); 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 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
This question is marked "community wiki".
asked 17 Jun '15, 22:56

because Tester and Setter solution not yet updated .... here is my code...
} End of code..................HAPPY CODING answered 22 Jun '15, 00:25

@rcsldav2017 press CTRL+K and start typing your code answered 22 Jun '15, 01:09
@shubham99 .... THANKS DUDE....IT WORKS
(22 Jun '15, 09:52)

I wonder how could this solution be accepted! It just prints "odd" if k equals 1, and prints "even" otherwise. answered 22 Jun '15, 01:34
lol, thats his luck
(22 Jun '15, 08:58)
@snk967: That happened because of some weak test cases at corner!
(22 Jun '15, 09:02)
IT WORKS SOME TIMES..YOUR CODE WORKS BUT U DON'T KNOW HOW IT WORK.. VERY WEAK TEST CASES....IT IS NOT GOOD AFTER SEEING VERY LOOSE TEST CASE..
(22 Jun '15, 09:56)

No array will be not like S, S+1, 2S+2, 4S+4, 8S+8, 16S+16. It will be like S, 2S+1, 4S+3, 8S+7, 16S+15..... kth term > S * ( 2 ^ ( k  1 ) ) + ( 2 ^ ( k  1 )  1 ). Then we can get answer by putting values of S and k. answered 22 Jun '15, 00:36

Can someone point out the mistake in my solution?
answered 23 Jun '15, 13:57
hi I have corrected your code and pointed out your mistake ...hope it is helpful to u....happy coding.................
(29 Jun '15, 12:54)

Number of test cases. Your code should run for Various test case T. You are not scanning that. answered 23 Jun '15, 20:16

We can also observe a pattern forming in the array. First, the sum of all elements in the array is computed to be S. Then, the array fans out as: S, S+1, 2S+2, 4S+4, 8S+8, 16S+16.... The kth term is equal to 2^(k1)*(S+1) So our answer is odd if and only if S is even and K is equal to 1. Complexity: O(N). answered 22 Jun '15, 00:23

@amitpandeykgp...how to paste code with indentation here... answered 22 Jun '15, 00:36

hi.... actually your logic is same as mine and
here what you have missed... just look at constraints
Hope you get your mistake ....still not...No problem MISTAKE
Solution
 there are multiple test cases.... look at 1<=T<=10 here is your corrected code..still did not get it ...click on me for more conversation join my group....Novice Programmers @ NITK Happy codinganswered 29 Jun '15, 12:52

public static String logicHere(String fileName){
BufferedReader br = null;
int opArr[];
int N=0;
int K=0;
String line2="";
String line3="";
int initialSum=0;
String retValue="";
try {
answered 01 Jul '15, 15:16

Why everyone is trying to take an array and then evaluate the sum. There's no need of it at all. We just need to look for number of odd elements in the array. if number of odd elements is even then sum is always even.if number of odd elements is odd them sum is always odd.
import java.math.*; import java.util.regex.Pattern; public class check {
Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t>0){ int n=sc.nextInt(); int k=sc.nextInt(); int count=0; for(int i=0;i<n;i++){ if(sc.nextInt()%2!=0){ count++; } } if(count%2==0){ if(k==1) System.out.println("odd"); else System.out.println("even"); }else{
} t; }
} answered 29 Oct '16, 00:12

include<bits stdc++.h="">using namespace std; int main() { int t; cin>>t; while(t) { int n,k; cin>>n>>k; long long s=0,a[n+5]; for(int i=0;i<n;i++) {="" cin="">>a[i]; s+=a[i]; } if(k==1) cout<<((s+1)%2?"odd":"even"); else if(k==2) cout<<((2*s+1)%2?"odd":"even"); else cout<<"even"; cout<<endl; } return 0; } answered 25 Dec '16, 17:32

Plz can someone point out mistake in my code plz.Here is my code: include<bits stdc++.h="">using namespace std; int main() { int t; cin>>t; while(t) { long long int n,k,i,s=0; cin>>n>>k; long long int a[n]; for(i=0;i<n;i++){
} answered 30 Dec '16, 12:12

using namespace std; int main() { int t; cin>>t;
} answered 21 Jul '18, 11:34

Here is my solution too short include<bits stdc++.h="">using namespace std; int main() { long long int t,n,k,i,s,a,p; cin>>t; while(t) {s=0; cin>>n>>k; for(i=0;i<n;i++) {="" cin="">>a; s+=a; } p=(s+1)*(long long int)pow(2,k1); if(p%2==0) cout<<"even"<<endl; else cout<<"odd"<<endl; } } answered 22 Jun '15, 10:54
