Given a random sequence of N numbers, a[0…N-1], sort them in order and report the difference between the sum of numbers in odd positions and the sum of numbers in even position.
If a quick sort is directly applied, the time complexity is O(N logN). But the range of numbers is small, within 1,000,000. Therefore, we can use the counting sort, that is,
count[0 .. 999999] = 0 for i = 0 to N-1 do count[a[i]] ++; end
Go through the count array again, we can get the order. With this algorithm, we can solve this problem in O(X) time, where X is the range of all numbers.