Problem Statement |
| | N candidates, indexed from 0 to N-1, participate in an election. After the voting is over, candidates are sorted by decreasing number of votes, and by increasing index in case of ties.
With the voting underway you have your favorites for different positions. You wonder how many additional voters would have to come to make your selection possible.
The int[] votes represents the results so far, where the k-th element is the number of votes received by candidate k.
The int[] wishList corresponds to the positions where you would like to see the candidates after the voting is over. If element k of wishList is -1, it means that you don't care where candidate k ends up. Otherwise, the number represents your desired 0-based position for candidate k.
Return the minimal number of additional votes needed to make it possible for the final ranking to match your wishes. |
| |
Definition |
| | | Class: | Election | | Method: | votesNeeded | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int votesNeeded(int[] votes, int[] wishList) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | votes will contain between 1 and 50 elements, inclusive. |
| - | wishList will contain the same number of elements as votes. |
| - | Each element of votes will be between 0 and 10,000,000, inclusive. |
| - | Each element of wishList will be between -1 and N - 1, inclusive, where N is the number of elements in votes. |
| - | Elements of wishList, other than -1, will be distinct. |
| |
Examples |
| 0) | |
| | | Returns: 6 | | If 3 more people vote for candidate 1, and 3 more people vote for candidate 3, the vote distribution would be {10,11,6,7}, and the final candidate ranking would be {1,0,3,2}, which matches your wishes. |
|
|
| 1) | |
| | | Returns: 31 | | Candidate 3 will need 31 votes to take the lead. |
|
|
| 2) | |
| | {10, 100, 40, 15, 15} | {4, 0, 1, 3, 2} |
| Returns: 1 | | It's almost as wished, but the tie breaker rule would make candidate 3 come before candadiate 4. One more vote is enough to fix that. |
|
|
| 3) | |
| | {5052863,4419975,3556783,9490441,6166389,836297,
4623556,4905465,117307,8071245,932463,9194925} | {-1,-1,-1,-1,2,0,-1,-1,8,9,4,11} |
| Returns: 53562445 | |
|