7
\$\begingroup\$

Given an array of non-negative integers, we need to find the sum of concatenation of elements in the array.

For example - given [11, 22] the result should be - 6666
i.e.,
11 + 11 = 1111
11 + 22 = 1122
22 + 11 = 2211
22 + 22 = 2222

Sum of all those numbers would result in 6666

My code is as below -

function concatenationsSum(a) {
  var sum = 0;
  for (var i = 0; i < a.length; i++)
    for (var j = 0; j < a.length; j++) 
        sum += Number("" + a[i] + a[j]);
  return sum;
}

Problems like these require brute force since we need to sum each and every combination. This works sure fine for smaller inputs. But if the array is longer, say, 1 ≤ lengthOfArray ≤ 25, how can I handle such large inputs faster? Any suggestions would be appreciated.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ What would be the expected result for an array with three or more elements? Is it still the sum of all combinations of two array elements? \$\endgroup\$ – Martin R Jul 31 '19 at 3:55
  • 1
    \$\begingroup\$ Btw, an array with 2^5 = 32 elements is not really “large.” \$\endgroup\$ – Martin R Jul 31 '19 at 6:13
  • \$\begingroup\$ @MartinR, sure the max length of the array would be 32, but the combinations I need to calculate the sum for would be 1024 \$\endgroup\$ – Prashanth kumar Jul 31 '19 at 14:04
  • 5
    \$\begingroup\$ Could you provide an example for three or four elements as well? Just to clarify how the concatenation should be done. \$\endgroup\$ – Simon Forsberg Jul 31 '19 at 19:27
  • \$\begingroup\$ (If this was tagged algorithm, I was tempted to suggest running totals by number "length".) \$\endgroup\$ – greybeard Feb 5 at 7:32
9
\$\begingroup\$

I'm always leery of the claim that problems require brute force algorithms. There is, for example, a formula for directly calculating the Nth Fibonacci number.

In the case of this problem, there is a much simpler way to perform the calculation that does not require O(n^2) time. Each element of the array pairs with every other element exactly twice - once as the most significant part, and once as the least significant part. These two parts can be calculated separately in one pass.

The low part is the sum of the elements times the number of elements.

The high part is the sum of (the "offset" for each element times the sum of the elements). The offset is the digit base raised to the number of digits (expressed generally, but this problem always uses base 10). So for a two digit number (11 or 22) the offset is 100.

function concatenationsSum2(a) {
    var lowSum = 0;
    for (var i = 0; i < a.length; i++)
        lowSum += a[i];

    var sum = lowSum * a.length;

    for (var i = 0; i < a.length; i++) {
        var size = a[i].toString().length;
        var offset = iPower(10, size);
        sum = sum + lowSum * offset;
    }

    return sum;
}

function iPower(base, power) {
    var result = 1;
    for (var i = 1; i <= power; i++)
        result *= base;

    return result;
}

And from there, we can simplify even further by combining the two parts.

function concatenationsSum3(a) {
    var lowSum = 0;
    var offsetSum = 0;
    for (var i = 0; i < a.length; i++) {
        lowSum += a[i];

        var size = a[i].toString().length;
        var offset = iPower(10, size);
        offsetSum += offset;
    }

    return lowSum * a.length + lowSum * offsetSum;
}
\$\endgroup\$
2
  • \$\begingroup\$ Yeah, if the user puts in numbers that overflow a 32 bit integer then the implementation has to ensure that the arithmetic is done with either 64 bit integers or some kind of "Big Int" library. The original question didn't ask about handling pathological test cases, so I think I can forgive myself for overlooking that. \$\endgroup\$ – Donald.McLean Jan 14 at 20:45
  • \$\begingroup\$ The 32 bit integer case has been solved by making the refactor to use Longs from the start: var lowSum = 0L. \$\endgroup\$ – Adam Hurwitz Jan 14 at 21:02
0
\$\begingroup\$

Try to convert before concatenating, it may be that directly concatenating 2 integers takes longer than concatenating 2 strings

sum += parseInt( a[i].toString.concat(a[j].toString() );

If you are looking to improve, you could assign a variable the size of the array, so that it does not do it in each cycle.

n = a.length;

for (var i = 0; i < n; i++)

It is better if for the conversion from Integer to String you do it previously, so you will not have to repeat conversions.

A solution in Php:

function concatenationsSum ($a) {
    $sum = 0;
    $n = count($a);
    for ($i=0; $i <$n ; $i++) { 
        $a[$i] = (string)$a[$i];
    }
    foreach($a as $v1) {
        foreach ($a as $v2) {
            $sum += (int)($v1 . $v2);
        }
    }
    
    return $sum;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to CodeReview@SE. In your first code block, the best clue whether this is something to avoid or something to strive for is digesting the code in your second block - it might be easier if you stuck to JavaScript. (The name of that other, um, language is PHP (started as an acronym).) \$\endgroup\$ – greybeard Feb 5 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.