Efficient algorithm to find the sum of all concatenated pairs

user_1470901 0
Viewed 8145

I took a practice CodeSignal exam and was able to pass 14/16 test cases for this problem. You are given a vector as input (list of ints) and the solution will be long long.

Originally I simply used a brute-force solution of two for loops and adding the current a[i] concat a[j] to a running total. However, I tried to optimize this by using memoization. I used a unordered_map of pairs to check if I already computed the (i,j) pair and if so, simply return the cached result. Even with my optimization, I still don't pass any additional test cases and receive a 14/16 result. What insight or optimizations am I missing?

I have found similar online problems, however their insight doesn't seem to be applicable to this specific problem.

Ex: Similar Problem

Question:

Given an array of positive integers a, your task is to calculate the sum of every possible concat(a[i], a[j]), where concat(a[i],a[j]) is the concatenation of the string representations of a[I] and a[j] respectively.

Ex:

a = [10,2]
sol = 1344
a[0],a[0] = 1010
a[0],a[1] = 102
a[1],a[0] = 210
a[1],a[1] = 22
sum of above = 1344

Code:

long long concat(int x, int y)
{
  string str = to_string(x)+to_string(y);
  return stoll(str);
}
long long calculateSum(vector<int> a)
{
  unordered_map<pair<int,int>,long long, hash_pair> memo;
  long long total = 0;
  for(int i = 0; i < a.size(); i++)
  {
    for(int j = 0; j < a.size(); j++)
    {
      auto currPair = make_pair(a[i],a[j]);
      auto got = memo.find(currPair);
      //if it's a new combination
      if(currPair == got.end())
      {
        long long res = concat(a[i],a[j]);
        memo.insert(make_pair(currPair,res));
        total += res;
      }
      //we've computed this result before
      else
      {
        total += got->second;
      }
    }
  }
  return total;
}
combinatorics algorithm c++
5 Answers

Let's calculate the contribution a_i integer to answer in all pairs. There are two cases. The first case when number a_i is low part. When total sum is n * a_i to answer (n is total number integers). The second case is high part. Then let's find all offsets in decimal notation. Denote by k_j as total number integers length j (length in decimal notation). Then high part add to answer k_j * a_i * 10^j for all value j (1 <= j <= 7). Knowing k_j we can calculate the answer for all numbers a_i in linear time.

user_19912730

I got the exactly same problem in an online assessment platform. The below python solution passed all test cases.

import collections
def concatenatSum(a):
    tot = 0
    dic = collections.defaultdict(int)
    for i in range(len(a)):
        _str = str(a[i])
        n = len(_str)
        dic[n]+=1
    
    for i in  range(len(a)):
        for k,v in dic.items():
            tot+=a[i]*(v*pow(10,k))
        tot+=(a[i]*len(a))
    
    return tot
user_72228230

Below Java solution passes all test cases I believe.

long concatenationsSum(int[] a) {
    long[] ans = new long[1];
    long[] total = new long[1];
    Map<Integer, Integer> powMap = new HashMap<>();
    for(int i = 0; i < a.length; ++i){
        int currentPow = (int)Math.log10(a[i]);
        powMap.put(currentPow, powMap.getOrDefault(currentPow, 0)+1);
        total[0] += a[i];
    }
    powMap.put(-1, a.length);
    powMap.forEach((key, val)-> ans[0] +=(long)Math.pow(10, key+1)*total[0]*val);
    return ans[0]; }
user_51353150

JS solution passed all test cases:

function concatenationsSum(arr) {
   let inimSum = 0;
   let offsetSum = 0;
   arr.forEach(el => {
      inimSum += el;

      const size = el.toString().length;
      const offset = Math.pow(10, size);
      offsetSum += offset;
   });

   return inimSum * arr.length + inimSum * offsetSum;
}
user_73944720

Here is a working Java/8-11 solution implementing the @aropan explantions :

 static long solution(int[] a){
    java.util.Map<Integer,Integer> intToLength = new java.util.HashMap();
    int len = a.length;
    int[] lengths = new int[len];//track the length of each elements to avoid including it when doing the k_j*a[i]*10^j calculation.
    for(int i=0; i<len; i++){
        int l = (int)Math.log10(a[i])+1;
        lengths[i] = l;
        intToLength.compute(l, (k, v) -> v == null ? 1 : v+1);
    } 

    long sum = 0;
    for(int i=0; i<len; i++){
        sum += len*a[i];
        //k_j*a[i]*10^j calculation
        long x = 0;
        for(var e : intToLength.entrySet()){
            int k_j = 0;
            if(lengths[i] == e.getKey())
                k_j--;//exclude a[i] length
            k_j+=e.getValue();
            x += k_j*a[i]*(long)Math.pow(10, e.getKey());
        }
        sum += x;
    }
    return sum;
}
user_29419010
Related