Python nested loop miscounting instances of integers in list

Question

I'm banging my head against the wall trying to figure out why this nested loop is miscounting the number of times an integer occurs in a list. I've set up a function to take two lines of input, n and ar, where n is the number of integers in ar and ar is the list of integers. My code is below:

import sys

n = sys.stdin.readline()
n = int(n)
ar = sys.stdin.readline()
ar = ar.split(' ')
ar = [int(i) for i in ar]

def find_mode(n,ar):
    # create an empty dict and initially set count of all integers to 1
    d = {}
    for i in range(n):
        d[ar[i]] = 1

    for i in range(n):
        # hold integer i constant and check subsequent integers against it
        # increase count if match
        x = ar[i]

        for k in range(i+1,n):
            if ar[k] == x:
                d[ar[k]] += 1

    print(d)

The counter seems to be increasing the count by 1 every time, which leads me to believe it's a problem with the nested loop.

>>> 9 
>>> 1 2 3 4 4 9 9 0 0
{0: 2, 1: 1, 2: 1, 3: 1, 4: 2, 9: 2}

OK

>>> 10
>>> 1 2 3 4 4 9 9 0 0 0
{0: 4, 1: 1, 2: 1, 3: 1, 4: 2, 9: 2}

Count of 0 increased by +2

>>> 11
>>> 1 2 3 4 4 9 9 0 0 0 0
{0: 7, 1: 1, 2: 1, 3: 1, 4: 2, 9: 2}

Count of 0 increased by +3

I understand there might be more efficient or "pythonic" ways to count the amount of times a number occurs in a list but this was the solution I came up with and as someone still learning Python, it would help to understand why this exact solution is failing. Many thanks in advance.

Answer 1

This is because for each distinct number in the list (call it x) you count the number of subsequent appearances. This is fine if a number only occurs twice but if it occurs multiple times you will over-count for each additional appearance.

For example: [0, 0, 0, 0]. You iterate over the list and then for each item you iterate over the list that follows that item. So for the first 0 you count a total of 3 subsequent 0s. For the second however you will count a total of 2 and for the third a total of 1 which makes 6. This is why you have 3 too much in the end.

You can achieve this task by using collections.Counter:

>>> from collections import Counter
>>> d = Counter(ar)