Differing pairs

Here is a $\Theta(n)$ solution:

• Put the numbers in the list in a Hash-table

• Go through each number $i$ in the list

• Check if $i+70$ is in the Hashtable and increment a counter variable if it is. We know that despite collisions this takes $O(1)$ via amortized analysis.

Below is a python implementation via a set object which is a hash-table.

1
2
3
4

with open('L1JKzVE9.txt','rb') as numbers:
    exec('List = set( '+numbers.read() + ')' ) #Extracting the numbers from the file

print len([ i for i in List if (i+70) in List])

1
2
3
4
5
6
7
8
9

s= text
def different(x):
    count = 0
    for i in x:
        for k in x:
            if i - k == 70:
                count = count + 1
    return count
print different(s)

This is my first try solving computer science problem any suggest please :)

Brute Force Approach: $O(n^{2})$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int dups(vector<int>& a, int k) {
    int cnt = 0;
    for(int i = 0; i < a.size()-1;i ++) {
        for(int j = i+1; j < a.size(); j++) {
            if(abs(a[j]-a[i]) == 70)
                cnt++;
        }
    }
    return cnt;
}

Two Pointers Approach: $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int dups(vector<int>& a, int k) {
    sort(a.begin(), a.end());

    int i = 0, j = 1;
    int cnt = 0;
    while(j < a.size()) {
        int n = abs(a[j] - a[i]);
        if(n == k) {
            cnt++;
            if(j < a.size()-1 && a[j] == a[j+1])
                j++;
            else if(i < a.size()-1 && a[i] == a[i+1])
                i++;
            else 
                i++;
        } else if(n > k) 
            i++;
        else 
            j++;
    }
    return cnt;
}

Here's a trivial $\Theta \left( { n }^{ 2 } \right)$ solution. I am working on improving my solution.

1
2
3
4
5
6

>>> n = [that array]
>>> count = 0
>>> for x in n:
        for y in n:
            count += x - y == 70
>>> print count

Surprising thing is that my solution still runs in a reasonable amount of time on my machine (about 6.92 secs).

By the way, isn't the question overrated? (400 points! whoa!)

I haven't done any timings or measurements of memory use; it's worth remembering though that building actual lists and sets (rather than using generators) takes time and space too.

And eval is naughty. ;)

1
2
3
4
5
6

numbers=[82048, ..., 85637]
s=(1 for i in numbers for j in numbers if i-j ==70)
count=0
for k in s:
    count+=k
print count

Python 3.4:

1
2
3
4
5
6
7
8
9

# convert text to array of integers
numbers = eval(open("numbers.txt", "r").read())
# count pairs with difference of 70
count = 0
for a in numbers:
    for b in numbers:
        if a - b == 70:
            count += 1
print ("Answer:", count)