Whats wrong in my approach (Reduction Game)

general
, , ,
21

My code is available here

An important testcase:

4 2
4 4 4 4

Ans: 10

I have explained my code in comments.

PS: If their are any corrections please suggest them.

22

Can you share, how did you arrive on that answer?

23

i guess ur approach is failing here :-
n=6 k=4
10 10 11 13 14 20

answer will be 40

24

@hemant_dhanuka

4 4 4 4

4 3 3 4

3 3 2 4

2 2 2 4

25

@mastersabh, got it bro

26

In your code, on lines 54 and 55, you’ve written “If the total is greater than x-1 element we can simply say that we will be able to reduce them to k.” How? Can you please explain?

Also, on line 47, I think you meant “modified x-1th element” instead of xth element.

27

Can anyone who got AC in this question is willing to share his approach ???

28

Refer this answer.

29

You can’t get more than 25

30

@meet2mky you can. Following these operations gives 29:

3 9 11 13 25
1 9 11 11 25
1 9 5 5 25
1 5 1 5 25
1 1 1 1 25
31

here is link to solution :

32

Sort-20 14 13 11 10 10
Red-20 13 12 11 10 10
Sort-20 13 12 11 10 10
Red-20 12 11 11 10 10
Sort-20 12 11 11 10 10
Red-20 11 10 11 10 10
Sort-20 11 11 10 10 10
Red-20 10 10 10 10 10
Sort-20 10 10 10 10 10
Red-20 9 9 10 10 10
Sort-20 10 10 10 9 9
Red-20 9 9 10 9 9
Sor-20 10 9 9 9 9
Red-20 9 8 9 9 9
Sort-20 9 9 9 9 8
Red-20 8 8 9 9 8
Sort20 9 9 8 8 8
Red20 8 8 8 8 8
Sort20 8 8 8 8 8
Red20 7 7 8 8 8
Sort20 8 8 8 7 7
Red20 7 7 8 7 7
Sort20 8 7 7 7 7
Red20 7 6 7 7 7
Sort20 7 7 7 7 6
Red20 6 6 7 7 6
Sort20 7 7 6 6 6
Red20 6 6 6 6 6
If you look the pattern the array will finally reduce to 20 4 4 4 4 4.