Voting Fraud (CHN16G) : Solution with hints

Hint 1:

Click to view

If a person votes more than once, the number of fraud votes from them are number of votes they make -1.
So if a person votes twice, one of their votes is fraud.

Hint 2:

Click to view

Each person’s id is \leq 100, so we can use a table to keep count of how many times each person has voted.
Like if sequence of votes is [1, 2, 3, 2] then count of votes is

0 -> 0

1 -> 1

2 -> 2

3 -> 1

Hint 3:

Click to view

How do you count the number of occurrences of a number in a list?

Hint 4

Click to view

You can run over the list, and every time you encounter the desired number, you increment a variable
where you are keeping count of its occurrences (which starts at 0).

Hint 5:

Click to view

How do you keep track of the number of occurrences of two numbers?

Hint 6:

Click to view

Same as above, but this time you keep two count variables, and have to compare each element
with two values.

Hint 7:

Click to view

How do you extend this approach to 100 numbers?

Hint 8:

Click to view

You can use a list to store 100 counts, but how would you know which value to increment?
100 comparisons is not feasible, we don’t want to write that much code.

Hint 9:

Click to view

You can use the value of an element as an index for the list.
So let us say you were using the list T to keep count of each number.
Then when you are running over the list of votes, say L = [2, 1, 3, 2, 3], then
at first element of L you increment T[2] by 1. At second element of L, you increment
T[1] by 1. Can you see a pattern here?

Hint 10:

Click to view

At L[i], we increment T[L[i]] by 1.