1

Today I was doing a simple challenge on HackerRank with the code below, which is 100% acceptable and works, but I was wondering if there was a way to even further reduce the loops required by eliminating duplicate calculations.

Let me show you visually what's happening, By the time I'm done, my code example is going to be very far down!

The code takes the first number in an array of numbers and adds it to each subsequent number and checks if its divisible by k = 3.

In an array of 6 numbers, that equates to 15 loops, which would be O(n²), meaning that my loops will grow exponentially to the amount of input. 7 numbers would be 21 loops.

P.S., you might be thinking that 6 should be 21 loops, and 7 should be 28, but keep in mind that I'm always taking the current number and adding it to the next, with the exception of the last number.

Visual Breakdown

input: [1, 3, 2, 6, 1, 2]

  • 1+3, 1+2, 1+6, 1+1, 1+2
  • 3+2, 3+6, 3+1, 3+2
  • 2+6, 2+1, 2+2
  • 6+1, 6+2
  • 1+2

Explanation

If you look at the numbers I've put in bold, you'll see they're duplicate calculations. The italics numbers are numbers divisible by k = 3. Now we're getting to my meat of my question. How can I eliminate this duplicate math, which would bring my loops down from 15 to 8 in this particular example. The algorithm would still have a worse case scenario of O(n²), if all the numbers were different, but this would be an optimization nonetheless.

Code Demo

function divisibleSumPairs(k, a) {
  let pairs = 0;
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if ((a[i] + a[j])/k % 1 === 0) pairs++;
    }
  }
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

Improve this question
9
  • SO is for specific programming problems. Your question is rather on-topic to CR than SO. Commented Nov 27, 2018 at 8:33
  • 2
    Congratulations! You just uncovered the wonderful world of dynamic programming! Now go pick up your copy of CLRS. Commented Nov 27, 2018 at 8:34
  • @hindmost, thanks for the heads up about CR. I was a bit on the fence about which place to post the question. Commented Nov 27, 2018 at 8:37
  • Thank you @EmilVikström, I actually already own that book. :) Commented Nov 27, 2018 at 8:38
  • if your need is to process all the combination there is no way to decrease number of loops. but what is goal you wanted to achieve? do you need to get amount of sums that divides by 3? or positions of numbers their sum % 3 === 0? or what? Commented Nov 27, 2018 at 8:54

2 Answers 2

Reset to default
3

I spent awhile thinking about how I can preprocess the array of numbers to prevent duplicate calculations, then I stepped away for a bit, and came back to the problem with a clear head and a cold drink of water.

Then I thought "What if I preprocess the divisor instead"?

The downside of this approach is that it creates and array of equal size to the divisor, but it does it in O(n) time complexity (screw space complexity, lol)

For this particular example we have 3 loops for the divisor, and 6 loops for the calculation, for a total of 9 loops, which is a savings of 6 loops over the original solution, and an elimination of O(n²).

This results in my function having an overall time complexity of O(n)

function divisibleSumPairs(k, a) {
  const mod = new Array(k).fill(0);
  let pairs = 0;
  
  for (let i = 0; i < a.length; i++) {
      const position = a[i] % k;
      
      pairs += mod[(k - position) % k];
      mod[position]++;
  }
  
  console.log(pairs);
}

divisibleSumPairs(3, [ 1, 3, 2, 6, 1, 2 ])

Performance Testing

I ran several iterations of my code through a performance test, I was surprised to see how much better a simple for loop compared to forEach and reduce.

  1. for^2: the original code
  2. for: the code in this post
  3. forEach: this post, using forEach instead
  4. reduce: this post, using reduce instead

https://jsperf.com/for-2-vs-for-vs-foreach-vs-reduce/1

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Perfect!! I came up with the same approach! +1
pairs += mod[k - position]; is sufficient because 0 <= position < k
k - position sometimes returns index positions above the length of mod, causing NaN due to a return of undefined from mod
0

To achieve this dynamic problem

Try to store the result in Object lets say sum_map if found this means we have already calculated this sum if not calculate the sum and store the result in map for future reference.

sample snippet:

let d = [1, 3, 2, 6, 1, 2]

const len = d.length

const sum_map = {}

let pairs = 0

for (let i = 0; i < d.length - 1; i++) {
  for (let j = i + 1; j < d.length; j++) {
    const key1 = `${d[i]}_${d[j]}`
    const key2 = `${d[j]}_${d[i]}`
    let result = 0
    if (sum_map[key1]) {
      result = sum_map[key1]
    } else if (sum_map[key2]) {
      result = sum_map[key2]
    } else {
      result = d[j] + d[i]
      sum_map[`${d[i]}_${d[j]}`] = result
    }
    if (result % 3 === 0) {
      pairs += 1
    }
  }
}
console.log(pairs)

In order to avoid O(n^2) simple trick is to know that

Example

lets say number you are checking with is 5 and arr = [1,3,2,6,1,2,5]

  1. you will only find sums divisible by the number if its numbers compliment remainder is present.

like for example number pair divisible by 5 are only ones which gives a compliment remainder i.e. 3 % 5 = 2 and 2 % 5 = 3 so the sum will be divisible by 5

so to solve this just find the compliment remainders and choose from them

like say you are 3 nums giving remainder 2 and 4 nums giving remainder 3

so pairs will choose 1 from those 3 nums * choose 1 from those 4 nums

  1. if number is divisible by 5 but if its only 1 its sum will never be divisible.

code snippet:

let d = [1, 3, 2, 6, 1, 2, 5]

const check_div_num = 5

remainder_map = {}

mod_arr = d.map((i) =>{
  const rem = i % 5
  if(remainder_map[rem]) {
    remainder_map[rem] += 1
  } else {
    remainder_map[rem] = 1
  }
  return rem
})

const till = Math.floor(check_div_num / 2)

keys = Object.keys(remainder_map)


let pairs = 0

for (let j = 0; j < keys.length; j++) {
  const key = keys[j]
  if(key === '0' && remainder_map["0"] > 1) {
    pairs += remainder_map[key] / 2
    continue
  }
  if(Number(key) <= till) {
    let compliment = remainder_map[check_div_num - Number(key)]
    const compliemnt_key = check_div_num - Number(key)
    if(compliment) {
      pairs += remainder_map[key]*remainder_map[compliemnt_key.toString()]
    } else {
      continue
    }
  } else {
    break
  }
}
console.log(pairs)

mind here I am only looping till half of 5 i.e. Math.floor(5/2) as we are already checking for their compliment

Improve this answer

8 Comments

I was thinking of doing the same (tracking previous calculations in a map), but it's still the same amount of loops. I'm thinking that some preprocessing of the original array will be required to cut down on the amount of loops.
I posted this approach as you question title said avoid duplicate calculations and ven if you pre-process the array for checking the rest items it will be O(n^2)
I appreciate your answer. The question is to do so in order to optimize time complexity, i.e, reduce loops.
I have updated the answer to find pairs based on compliment method
I doubt the sum_map helps - string concatenation and object lookup are much more expensive than a simple addition. The compliment remainder approach is a good solution though.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.