Was able to pass the test, however I think there is a bug in the solution of the algorithm

interview-questions
Tags: #<Tag:0x00007f242d6f0a88>

#1

As I understand the algorithm is to go beyond the target till the running sum-target is even. the logic is by flipping the ((sum-target)/2)th step we are guaranteed to reach the target.

Don’t we need to ensure k in 2*k is less than step(k<steps). As we can only do this flipping if k < less than step. If we never reached the step we cant negate it.

For example number 42. The progression would be
step1: add 1-> 1
step2: add 2-> 3
step3: add 3-> 6
step4: add 4-> 10
step5: add 5-> 15
step6: add 6-> 21
step7: add 7-> 28
step8: add 8-> 36
step9: add 9-> 45(45-42 is odd)
step10: add 10-> 55(55-42 is odd)
step11: add 11-> 66(66-42=2*12).
=> k=12 or (1+ 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 - 2x12 = 42 )
you need to flip the 12th step in a total of 11 steps?


#2

Can you explain me the flipping part. I am not able to get it, Also the solution does not workl for N = 4.