problem with implementation of partition problem from jan long

general
,
1

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

2

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
3

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
4

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
5

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.

6

thanks bro it worked.
i check what i did wrong there.

7

thanks for the tc @inovation123

8

Hey @vikaskodag98 :slight_smile: 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
9

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