DistancesBetweenNumbers

Given two non-negative integers X and Y, their distance is defined as the number of base-10 digits in which they differ.

For example:

• distance(47, 47) = 0
• distance(42, 47) = distance(47, 42) = 1: these numbers have the same tens digit and different ones digits
• distance(24, 42) = 2: we are comparing each position separately, not just the sets of digits
• distance(1234, 37) = 3: if one number is shorter, the missing digits are zero, so distance(1234, 37) = distance(1234, 0037)

You are given a long sequence A that consists of N non-negative integers.

For each pair of indices i and j (0 <= i < j < N), Lucy calculated the distance between A[i] and A[j]. Then, Lucy computed the sum of all those distances.

Return the final value obtained by Lucy.

In order to keep the input size small, you are only given a prefix of A, the rest is generated pseudorandomly. Please use the pseudocode or code given below to generate A.

Pseudocode:

A = an empty array of length N
L = length(Aprefix)

for i = 0 to L-1:
    A[i] = Aprefix[i]

for i = L to N-1:
    A[i] = (A[i-1] * 1103515245 + 12345) modulo 2^31

-------------------------------------------------------------------------------------

Java:

int[] A = new int[N];
int L = Aprefix.length;
for (int i=0; i<L; ++i) A[i] = Aprefix[i];
for (int i=L; i<N; ++i) A[i] = (int)((A[i-1] * 1103515245L + 12345L) % (1L << 31));

-------------------------------------------------------------------------------------

C++:

vector<int> A(N);
int L = Aprefix.size();
for (int i=0; i<L; ++i) A[i] = Aprefix[i];
for (int i=L; i<N; ++i) A[i] = (A[i-1] * 1103515245LL + 12345LL) % (1LL << 31);