Count total of number array with ignoring overlap number

user_2457026 0
Viewed 122

I have this kind of problem and trying to solve it by using Javascript/Go. Given this array of number set, I would like to find the sum of number. The calculation should ignore the overlap and consider to count it as only once.

const nums = [[10, 26], [43, 60], [24,31], [40,50], [13, 19]]

It would be something like following if translated into the picture.

enter image description here

The result should 41

The rules are

  • Overlap set of number (pink area) should be count once.
  • Count total sum of green area.
  • Total for both.

Any help will be appreciated.

go math arrays algorithm javascript
4 Answers

Here's an one-liner solution using javascript (Assuming the correct answer is 41 instead of 42).

The idea is to iterate all interval numbers and put them in a single array, then trim all the duplicates using Set. The time complexity is not optimal but it's short enough.

const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]];

const total = new Set(nums.reduce((acc, [from, to]) => 
  [...acc, ...Array.from({ length: to - from }, (_, i) => i + from)], [])).size;

console.log(total);

Not sure how to do it with go but it's just a proposal.

user_102892650

Here's my version:

const getCoverage = arr => arr
  .reduce((results, el) => {
    if (!results.length) { 
      return [el];
    }
    let running = true, i = 0;
    while(running && i < results.length) {
      if (el.some(n => n >= results[i][0] && n <= results[i][1])) {
        results[i] = [
          Math.min(el[0], results[i][0]),
          Math.max(el[1], results[i][1])
        ];
        running = false;
      } 
      i++;
    }
    if (running) {
      results.push(el);
    }
    return results;
  }, [])
  .reduce((total, el) => el[1] - el[0] + total, 0);

console.log(
  getCoverage([[10, 26], [43, 60], [24,31], [40,50], [13, 19]])
);

The first reducer merges overlapping (and adjacent) intervals and the second one adds up the diffs from the resulting merged ones.

user_18916770

You could sort the pairs and reduce by checking the second value and then add the deltas for getting the sum.

const
    nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]],
    result = nums
        .sort((a, b) => a[0] - b[0] || a[1] - b[1])
        .reduce((r, [...a]) => {
            const last = r[r.length - 1];
            if (last && last[1] >= a[0]) last[1] = Math.max(last[1], a[1]);
            else r.push(a);
            return r;
        }, [])
        .reduce((s, [l, r]) => s + r - l, 0);

console.log(result)

user_14476750

You can spread the values of given 2-D array in an array and sort both of them. Find the sum of the differences between the edge values of non-overlapping arrays and the sum of difference of values within overlapping area and the result will be the difference between the two.

const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]]
let arr = []
//spread given 2-D array
nums.forEach(item => arr=[...arr,...item]);
// Sort both arrays
arr.sort();
nums.sort();
let previtem, sum = 0;
let min , max ;
let count = 0;
//Loop to find sum of difference between non-overlapping values
nums.forEach((item,index) => {
        if (index === 0) {
           min = nums[0][0], max = nums[0][1]     
        }
        else if (!(item[0]>min && item[0]<max) && !(item[1]>min && item[1]<max))
        {
                flag = 1;
                count = count + (item[0] - max);
                min = item[0];
                max = item[1];
                console.log(item,count);
        }
        else if (item[0]>min && item[0]<max &&  !(item[1]>min && item[1]<max)) {
                max = item[1];
        }
})

// loop to find sum of difference of unique values within overlapping area
arr.forEach(item => {
        if (previtem && item !== previtem) {
                sum=sum+(item-previtem)
        }
        previtem = item;
})

//Print the result
console.log(sum - count);
user_163930020
Related