Finding an element without pair in a list O(n**2) I'm practicing algorithms, and I just can not come up with a faster solution to this problem, but I'm not hitting the benchmark.
Problem: In a large list of large integers, I must find the one element, that is present in odd numbers. E.g. [1,1,1,1, 2,2, 3,3,3, 4,4,4,4].
I wrote several solutions, but I can not increase the speed of the execution.
import random

def testdata():
  space = []
  for i in range(10000):
    space = (
        space
        + [random.randint(0,1000000000)]
        * (random.randint(1,10) * 2)
    )
  odd = random.randint(0,1000000000)
  print(odd)
  space = space + [odd]
  random.shuffle(space)
  return space


def solution(A):
  A.sort()
  index = 0
  while True:
    count = A.count(A[index])
    if count%2:
      return(A[index])
    else:
      index = index + count


def solution_b(A):
  for elem in set(A):
    if A.count(A)%2:
      return(elem)

I'm not only looking for a better solution, but I'd appreciate it if someone explained, how to approach this kind of Big O notation problems. Without using pandas or numpy, etc.
This is not a review, but an extended comment.
The linear time/constant space solution is too well known to be spelled out again. However, here it goes.
XOR of two equal numbers is 0, and XOR of a number and 0 leaves the number unchanged. XOR is commutative and associative operation; we may perform it in any order we wish, and arrive to the same result. In other words, if we XOR all of them, each pair of numbers would cancel to 0, and the final result would be the number without a pair, the one we are looking for.