Problem Statement
Elly and Kris are going to play a variant of the game Nim. The rules are as follows: In front of the players are N piles with stones. The number of stones in the piles are A[0], A[1], ..., A[N-1]. The players take alternating turns. In each turn the active player chooses exactly one non-empty pile and removes one or more stones from that pile (possibly all of them). The player, who takes the last stone, wins.
Elly goes first. This makes Kris think her friend has an advantage. Thus, Kris has decided to secretly add zero or more stones to some of the piles (possibly all or none of them) such that she can win even if Elly plays optimally. She can add different amounts of stones to different piles. More formally, Kris will choose some non-negative integers X[0], ..., X[N-1] and then she will add X[0] stones to pile 0, X[1] stones to pile 1, and so on. Thus, when the game starts, the piles will contain (A[0] + X[0]), (A[1]+X[1]), (A[2]+X[2]), ... stones.
Kris does not want things to look suspicious, thus she wants to minimize the total number of added stones (i.e., the sum of all X[i]). You are given the initial numbers of stones in the piles in the int[] A. Return the smallest total number of stones Kris needs to add so that she can guarantee that she will be able to win the game.
Definition
- Class:
- EllysNimDiv2
- Method:
- getMin
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int getMin(int[] A)
- (be sure your method is public)
Notes
- For the constraints specified below a solution always exists.
Constraints
- A will contain between 2 and 50 elements, inclusive.
- Each element of A will be between 1 and 1,000, inclusive.
Examples
{42, 13, 123, 55, 666, 17}Returns: 480
One possible solution is, for example, X[0] = 0, X[1] = 11, X[2] = 389, X[3] = 73, X[4] = 6, X[5] = 1. Although there exist other solutions with different X[0]...X[5], the total number of added stones in any valid solution is at least 480.{1, 1}Returns: 0
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}Returns: 4
{371, 740, 211, 798, 82, 385, 979, 389, 31, 667, 541, 561, 471}Returns: 42
{769, 727, 657, 924, 879, 674, 652, 995, 947, 896, 869, 553, 954, 974, 681, 768, 913}Returns: 666
{543, 230, 421, 415, 271, 962, 677, 373, 951, 114, 379, 15, 211, 955, 66, 573, 982, 296, 730, 591, 750, 877, 224, 186, 398, 84, 542, 770, 288, 78, 373, 417, 476, 968, 564, 565, 740, 377, 633, 287, 111, 823}Returns: 44