### PROBLEM LINK:

**Author:** Shiplu

**Tester:** Mahbubul Hasan

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Simple

### PREREQUISITES:

Sort

### PROBLEM:

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.

### EXPLANATION:

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.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.