Optimize this function

whats wrong with the code I wrote, its passing 14/16 tests but theres two its failing due to timeout. at first I added them all to an array and reduced the array, I realized I can just add them in place and not have to do that, yet it still fails. I dont have access to the tests that it is failing because Im using the free trial on this platform, heres the code I wrote:

image

Is there a problem with converting the string into a number?

1 Like

Please post your actual code instead of picture. Thanks

1 Like
function solution(a) {
  let sum = 0;
  for (let i = 0; i < a.length; i++) {
    const num = array[i];
    for (let j = 0; j < a.length; j++) {
      const secondNum = a[j];
      sum += Number(`${num}${secondNum}`);
    }
  }
}
1 Like

How long are these arrays?

You can trim somewhat by adding in pairs.

I dont know its from their daily timed free practice tests. the solution only got a 250/300. I cant see all the tests unless im a paying member. It passed the tests I was able to see.

I didnt understand can you please explain a bit more… thanks

If you have arr[i] and arr[j], might as well add them both in both orderings at the same time.

can you please explain more,

I have arr[i] that I can access in the inner loop and I thought im using it effectively, I cant access arr[j] in outer loop.

If you mean to say that I should calculate that in the outer loop than in the inner loop I will still have to do a check to see if i===j and if so then I will skip over that, so how does that save me any work as I still have to do a check in the inner loop? or maybe you mean for me to use some sort of memoization.

I was wrong before when I said I didnt know, I think they will have no more than 105 items

Input/Output

[execution time limit] 4 seconds (js)

[input] array.integer a

A non-empty array of positive integers.

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ 106.


The sum of all a[i] ∘ a[j]s. It's guaranteed that the answer is less than 253.


Can you rework your logic to start j at i + 1? It wouldn’t change your complexity class, but would cut down the constant a fair amount.

As a general rule, you should make the most of it when you have grabbed values out of your data structure.

Sorry, this is a bit cleaner, you can likely still optimize here and there. I think this is what the other user suggested.

function solution(a) {
  let sum = 0;
  for (let i = 0; i < a.length; i++) {
  const num = a[i];
  sum+=Number(`${num}${num}`);   
    for (let j = i + 1; j < a.length; j++) {
      const secondNum = a[j];
      sum += Number(`${num}${secondNum}`) + 
                       Number(`${secondNum}${num}`)
    }
  }
  return sum
}
solution([10,2])

The ideas are 2:

  • compute the “same-element in the outer loop” and then compute the [i][j] and [j][i] at once.

You can try in the browser.

2 Likes

I was dealing with some problem where I needed to get all possible pair sums of array items, and I was able(with some help from this forum) to figure out solution with single loop, not with nested loops.

I will try to apply that approach to your case.

I think you are correct, maybe this:

Wrong idea but keeping it for anyone learning, good to see what does not work…

function solution(a) {
  let sum = 0;
  let i = 0;
  for (i; i < a.length-1; i++) {
  const num = a[i];
  sum+=Number(`${num}${num}`);   
  const secondNum = a[i+1];
  sum += Number(`${num}${secondNum}`) + 
  Number(`${secondNum}${num}`)
  };
  const lastItem = a[i];
  return sum + Number(`${lastItem}${lastItem}`)
}
solution([10,2])

It probably needs some adjusting.

Your solution gives correct result for [10, 2] that’s for sure.

I came up with some while loop, also getting 1344 for [10,2], code needs some clean up also.

function solution(a) {
  let [first, second, len, sum] = [0, 0, a.length, 0];
  let pairSum;
  while (first < len && second < len) {
    if (first === second) {
      pairSum = Number(String(a[first]) + String(a[second]));
      sum += pairSum;
    }
    else {
      pairSum = Number(String(a[first]) + String(a[second]));
      sum += pairSum;
      pairSum = Number(String(a[second]) + String(a[first]));
      sum += pairSum;
    }
    if (first === len - 1 && second === len - 1) {
      return sum;
    }
    else if (second === len - 1) {
      first++;
      second = first;
    }
    else {
      second++;
    }
  }
}

And by the way, if we would need to find just sum of all possible pair sums(meaning we would need just to deal with numbers, not strings), it can be done with some maths just like that:

const sumOfAllPairSums = (arr) => {
  return arr.reduce((sum, curr) => sum + (curr * 2 * arr.length), 0);
}


console.log(sumOfAllPairSums([1, 2]));//12
1 Like

https://stackoverflow.com/questions/62397126/efficient-algorithm-to-find-the-sum-of-all-concatenated-pairs

1 Like

I wonder if using Math.pow can be considered optimized. But certainly an interesting solution.

I don’t think math.pow is needed for that algorithm described on stackoverflow? It should require a log10. In and case, adding a pow or a log is a fair trade to go from n^2 to n.

Edit: oh, 10^j is where the pow comes in. That shouldn’t be expensive though.

I don’t know if the function I suggested passes tests (no idea where the ex. came from) but it is not using any log or pow and a single loop.

There is though, the type conversion, which is ugly.

I’m not sure yours works. How would it handle a list of 100 values? Would it get every pair?

Oh, no, you are correct, it won’t calculate a[i] and a[i+2] etc. My bad.

Thanks. I think the first one, that you suggested, is fine.

I don’t have any test cases for this problem, but I tested your and my solution for

const arr = [1, 2, 3, 4, 5, 6];

For my solution I am getting 1386, for yours 616.

So our solutions are not the same and they are doing different thing, that’s for sure

Not for the first one suggested. The first one gives 1386. The second one, yes, for the reason I stated above. I had a brain-fart and compared all Xs with the next one.