Find Arrays In An Array

If a number occurs $k>1$ times in the array, then we have $k\choose 2$ ways to pick that number as the first and last number of the sub-array. Hence, the answer is

$\sum _{x\in set(A)} {k_x \choose 2}$

In other words, for each unique number, we count its frequency and sum the number of ways to be selected as the first and last number of the sub-array.

Now, how do we implement this? A sneak peak into the test data gives us a sense that the numbers are huge (roughly $10^9$ ). Hence we will use a map data structure to store the frequency of the numbers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>
using namespace std;

int N;
map<long long, long long> m;

int main() {

    scanf("%d",&N);
    for (int i = 0; i < N; i++) {
        long long x;
        scanf("%lld",&x);

        m[x]++; // keep track of frequency
    }

    long long ans = 0;
    // loop through all unique numbers
    for (map<long long, long long>::iterator it = m.begin(); it != m.end(); it++) {
        long long k = it->second;

        if (k < 2) continue;

        ans += k * (k - 1) / 2; // similar to k choose 2
    }

    cout << ans << endl;

    return 0;
}

This code returns $648349$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Compute n choose 2
def nc2 n
    n * (n-1) / 2
end

# Read all the numbers
nums = File.read('AinA.txt').split.map(&:to_i)
# Forget the first number
nums.shift
# Create a hash mapping each number to the number of time it occurs
nums_hash = nums.inject(Hash.new(0)) { |total, e| total[e] += 1 ; total }
# Sums the nc2 of all values of the hash
nums_hash.values.map { |i| nc2 i }.inject :+

The algorithm is O(n) . It count the number of occurrences of each number in the file and uses that to compute the number of sub arrays possible.

Key Idea : If a number occurs x number of times, then the number of sub arrays starting and end at that number is n choose 2 .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

filee = open("/Users/davidholcer/Desktop/A/AinA.txt", "r") #opens file with name of "AinA.txt"
n=filee.readline()
nums=filee.readline().split(" ")
used=[]
total=0
c=0
while c < len(nums):
    if nums[c] not in used:
        x=nums.count(nums[c])
        total+=((x*(x-1))/2)
        used.append(nums[c])
    c+=1
print total

If number x appears n times, there are n(n-1)/2 ways to pick numbers one apart, two apart... all the way to n-1 apart, where numbers can be in between. Knowing this you just need to count the number of occurrences (x) of any given number, (making sure not to count a number twice) and use the formula f(x)=x(x-1)/2 to find the total arrays for x. Adding all values of all f(x) we obtain the total.