How to perform j operations on array?

Question

Given an array of integers, what's the most efficient way to perform j operations on the array where the value of j could be => or <= array.length?

I tried something like this...

function performJ(arr, j) {
  arr.sort((a, b) => b - a);
  let i = 0;
  while (j !== 0) {
   if (i < arr.length) {
     arr[i] = Math.ceil(arr[i] / 2)
   } else {
     // when i reaches arr.length, reset it to continue operations j
     i = 0;
     arr[i] = Math.ceil(arr[i] / 2)
   }
   // increment i, step through arr
   ++i;
   // decrement j as we perform operations on arr
   --j;
 }
 return arr.reduce((a, b) => a + b);
}

That works for a lot of cases, but for some reason it seems like large inputs of arr and j cause arithmetic operations in the while loop to get way off.

Thanks!

EDIT: Edited question for clarity. I previously had a solution that worked, but it took way too long. This solution's arithmetic is off, but works much faster.

"the most efficient way" in terms of what? Also what is `arr.someMethod();`? — Yury Tarabanko, Apr 11 '20 at 00:07
@Dekel -- Small inputs of `arr` and `j` work for something like sorting the array and reducing the sum of its elements, very large inputs produce incorrect answers for those operations. — joehdodd, Apr 11 '20 at 00:11
Can you give an example of such an input for which the result is incorrect? I tried a few but they seemed to work as desired — CertainPerformance, Apr 11 '20 at 00:27
If you want a solution for the first paragraph, then check out @CertainPerformance 's answer. Your numbers going way off has nothing to do with the first paragraph. Your array of integers aren't really integers but double precision floats and is causing this problem: https://stackoverflow.com/questions/11695618/dealing-with-float-precision-in-javascript If you really want to work with integers, use the new BigInt type or use an arbitrary precision math library. — Kerim Güney, Apr 11 '20 at 00:33
The `i` is guaranteed to be an integer. The second argument `j` sounds like it should be as well, even if the number is large. — CertainPerformance, Apr 11 '20 at 00:37
@CertainPerformance Yep, the elements of `arr` are guaranteed to be integers, so is `j` — joehdodd, Apr 11 '20 at 00:44
I don't think it's `j` and `i` that stop being integers but the result of this expression `arr[i] / 2` , which is why I'm guessing OP added `Math.ceil()` around it. — Kerim Güney, Apr 11 '20 at 01:09
@KerimGüney -- the values returned when the function completes are integers, but they're incorrect in that they're much larger than the expected values. For the small inputs, the values are correct, for large inputs some return values are far greater than expected. — joehdodd, Apr 11 '20 at 12:04

score 4 · Answer 1 · answered Apr 11 '20 at 00:06

4

Use modulo to iterate on indicies [i % arr.length] from 0 to j:

function performJ(arr, j) {
  arr.someMethod(); // ?
  for (let i = 0; i < j; i++) {
    arr[i % arr.length] = /* operation */
  }
  return arr.someMethod(); // ?
}

answered Apr 11 '20 at 00:06

CertainPerformance

356,069
52
309
320

2

When `j` exceeds array length, it simply loops back to the remainder value (aka modulus). Not sure why there's a downvote tho... :/ this is a great answer. – Terry Apr 11 '20 at 00:14
Oddly enough, this solution fails in just the same way as my original code. I updated my question for more clarity on what I'm trying to do. My first solution worked, but took too long, so it's not a true "solution", but the one I shared above fails on larger inputs. – joehdodd Apr 11 '20 at 00:25

score 0 · Answer 2 · answered Apr 11 '20 at 00:13

Why not just a for loop like this?

for(let i = 0; i <= j; i++) {
  const index = i % array.length;
  array[index] = doSomething();
}

if array.length is 5 but j is 3 then doSomething() will only be called on the first three elements. if array.length is 3 but j is 5 then i will reach 3 and 3 % 3 === 0 so index will loop back to the beginning. That means doSomething() will be called on all three elements once and during the second run on only the first two elements.

Is this what you want?

How to perform j operations on array?

2 Answers2