Guys can anyone point out the problem in my implementation of partition problem.

I wrote two implementation with same logic and both gave wa on diff set of tcs.

implementation 1 : here

implementation 2 : here

Thanks in advance.

It will help me a lot

In you first solution, you have taken variable i as int then it could be overflow that’s why you got wrong answer.

1 Like

counter case for 2nd implementation is: n = 15, x = 12

I would suggest to generate some random input and test your program if you get wrong answer and are unable to figure it out

Hope this helps

1 Like

The solution for 2nd implementation would work if you would write **else if instead of if** when you are checking that whether **sum is greater than i** or not.

1 Like

i think variable i wouldnt overflow because i can never greater than n.

and constraints on n are 2 ≤ N ≤ 1,000,000.

if you found anything else tell or if i am leaving anything in my implementation.

thanks bro it worked.

i check what i did wrong there.

thanks for the tc @inovation123

Hey @vikaskodag98 Well your second implementation is a bit buggy. **It will fail at some test cases like: 24,32 ; 12 15 ; 65 90 etc…** Suppose the test case is (12,15) then your program will evaluate ‘sum’ initially as 54. Since you are iterating from last number i.e. 15, a[15]=1 (as sum= 54 is well greater than i=15) and it continues till i=13 where sum remains to be 25. Here your program decrements i as (sum-i)==x gets true(since x=12 here).

Now you are left with i=12 and sum= 25 and since (sum>i) gets true in your second if block **you evaluate a[12]= 1 which is wrong.**

1 Like

thanks for pointing out the mistake @ayush_0101. It was a silly mistake i overlooked.