Efficient algorithm to find the sum of all concatenated pairs of integers in a list

Question

I had this problem in one of my interview practices and had a problem getting this with a better time complexity other than O(N^2). At some level you'll have to visit each element in the list. I thought about using hash table but it would still have to conduct the hash table and populate it then do the calculation. Basically my solution was a nested for loop and I have my code included as well and it passed everything except time exception under 4 seconds.

My Code:

def concatenationsSum(a):
    sum = 0
    current_index_looking_at = 0
    for i in a:
        for x in a:
            temp = str(i)+str(x)
            sum += int(temp)
    return sum

The problem description:

Given an array of positive integers a, your task is to calculate the sum
of every possible a[i] ∘ a[j], where a[i] ∘ a[j] is the concatenation
of the string representations of a[i] and a[j] respectively.
    
    Example
    
    For a = [10, 2], the output should be concatenationsSum(a) = 1344.
    
    a[0] ∘ a[0] = 10 ∘ 10 = 1010,
    a[0] ∘ a[1] = 10 ∘ 2 = 102,
    a[1] ∘ a[0] = 2 ∘ 10 = 210,
    a[1] ∘ a[1] = 2 ∘ 2 = 22.
    So the sum is equal to 1010 + 102 + 210 + 22 = 1344.
    
    For a = [8], the output should be concatenationsSum(a) = 88.
    
    There is only one number in a, and a[0] ∘ a[0] = 8 ∘ 8 = 88, so the answer is 88.
    
    Input/Output
    
    [execution time limit] 4 seconds (py3)
    
    [input] array.integer a
    
    A non-empty array of positive integers.
    
    Guaranteed constraints:
    1 ≤ a.length ≤ 10^5,
    1 ≤ a[i] ≤ 10^6.
    
    [output] integer64
    
    The sum of all a[i] ∘ a[j]s. It's guaranteed that the answer is less than 2^53.

Answer 1

The concatenation of two integers:

m ∘ n

is equal to:

10**digit_length(n) * m + n

so the sum of the concatenations of every list item with a given integer:

(a[0] ∘ n) + (a[1] ∘ n) + …

is equal to:

(10**digit_length(n) * a[0] + n) + (10**digit_length(n) * a[1] + n) + …

and you can put all the ns on one side:

(10**digit_length(n) * a[0]) + (10**digit_length(n) * a[1]) + … + n + n + …

and note that each element of the array is multiplied by a value that only depends on n:

10**digit_length(n) * (a[0] + a[1] + …) + n + n + …

simplifying again:

10**digit_length(n) * sum(a) + len(a) * n

sum(a) doesn’t change, and the sum of len(a) * ns across all ns is len(a) * sum(a):

def concatenationsSum(a):
    sum_a = sum(a)
    return sum(10**digit_length(n) * sum_a for n in a) + len(a) * sum_a


def digit_length(n):
    """
    The number of base-10 digits in an integer.

    >>> digit_length(256)
    3

    >>> digit_length(0)
    1
    """
    return len(str(n))

This runs in linear time when the upper bound on the integers involved is constant. You can also use math.log10 to make digit_length faster as long as floating-point math is precise enough for the integer sizes involved (and if not, there are still better ways to implement it than going through a string – but probably no shorter or more understandable ways).