Given an array [[1, 7, 3, 8],[3, 2, 9, 4],[4, 3, 2, 1]], how can I find the sum of its repeating elements? (In this case, the sum would be 10.)

Repeated values are - 1 two times, 3 three times, 2 two times, and 4 two times So, 1 3 2 4 = 10

Need to solve this problem in the minimum time

There are multiple ways to solve this but time complexity is a major issue.

I try this with the recursion function

How can I optimize more

`

var uniqueArray = []
var sumArray = []
var sum = 0
function sumOfUniqueValue (num){
 
    for(let i in num){

        if(Array.isArray(num[i])){
            sumOfUniqueValue(num[i])
        }

        else{
            // if the first time any value will be there then push in a unique array
            if(!uniqueArray.includes(num[i])){
               uniqueArray.push(num[i])
            }
            // if the value repeats then check else condition
            else{ 
                // we will check that it is already added in sum or not 
                // so for record we will push the added value in sumArray so that it will added in sum only single time in case of the value repeat more then 2 times
                if(!sumArray.includes(num[i])){
                    sumArray.push(num[i])
                    sum =Number(num[i])
                }
            }
        } 
    }
}

sumOfUniqueValue([[1, 7, 3, 8],[1, 2, 9, 4],[4, 3, 2, 7]]) 
console.log("Sum =",sum)

` That's a real problem, I am just curious to solve this problem so that I can implement it in my project.

If you guys please mention the time it will take to complete in ms or ns then that would be really helpful, also how the solution will perform on big data set.

Thanks

CodePudding user response：

I would probably use a hash table instead of an array search with .includes(x) instead...

And it's also possible to use a classical for loop instead of recursive to reduce call stack.

function sumOfUniqueValue2 (matrix) {
  const matrixes = [matrix]
  let sum = 0
  let hashTable = {}

  for (let i = 0; i < matrixes.length; i  ) {
    let matrix = matrixes[i]
    for (let j = 0; j < matrix.length; j  ) {
      let x = matrix[j]
      if (Array.isArray(x)) {
        matrixes.push(x)
      } else {
        if (hashTable[x]) continue;
        if (hashTable[x] === undefined) {
            hashTable[x] = false;
            continue;
        }
        hashTable[x] = true;
        sum  = x;
      }
    }
  }

  return sum
}

const sum = sumOfUniqueValue2([[1, 7, 3, 8],[[[[[3, 2, 9, 4]]]]],[[4, 3, 2, 1]]]) // 10
console.log("Sum =", sum)

This is probably the fastest way...

But if i could choose a more cleaner solution that is easier to understand then i would have used flat sort first, chances are that the built in javascript engine can optimize this routes instead of running in the javascript main thread.

function sumOfUniqueValue (matrix) {
  const numbers = matrix.flat(Infinity).sort()
  const len = numbers.length
  let sum = 0

  for (let i = 1; i < len; i  ) {
    if (numbers[i] === numbers[i - 1]) {
      sum  = numbers[i]
      for (i  ; i < len && numbers[i] === numbers[i - 1]; i  );
    }
  }

  return sum
}

const sum = sumOfUniqueValue2([[1, 7, 3, 8],[[[[[3, 2, 9, 4]]]]],[[4, 3, 2, 1]]]) // 10
console.log("Sum =", sum)

CodePudding user response：

You could use an objkect for keeping trak of seen values, like

seen[value] = undefined // value is not seen before
seen[value] = false     // value is not counted/seen once
seen[value] = true      // value is counted/seen more than once

For getting a value, you could take two nested loops and visit every value.

Finally return sum.

const
    sumOfUniqueValue = (values, seen = {}) => {
        let sum = 0;
        
        for (const value of values) {
            if (Array.isArray(value)) {
                sum  = sumOfUniqueValue(value, seen);
                continue;
            }

            if (seen[value]) continue;

            if (seen[value] === undefined) {
                seen[value] = false;
                continue;
            }

            seen[value] = true;
            sum  = value;
        }
        return sum;
    },
    sum = sumOfUniqueValue([[1, 7, 3, 8], [3, 2, 9, 4], [4, 3, 2, 1]]);
    
console.log(sum);

Alternatively take a filter and sum the values. (it could be more performat with omitting same calls.)

const
    data = [[1, 7, 3, 8], [3, 2, 9, 4, 2], [4, 3, 2, 1]],
    sum = data
        .flat(Infinity)
        .filter((v, i, a) => a.indexOf(v) !== a.lastIndexOf(v) && i === a.indexOf(v))
        .reduce((a, b) => a   b, 0);

console.log(sum);

CodePudding user response：

You can flatten the array, filter-out single-instance values, and sum the result:

const data = [
    [ 1, 7, 3, 8 ],
    [ 3, 2, 9, 4 ],
    [ 4, 3, 2, 1 ]
];

const numbers = new Set( data.flat(Infinity).filter(
    (value, index, arr) => arr.lastIndexOf(value) != index)
);

const sum = [ ...numbers ].reduce((a, b) => a   b, 0);

Another approach could be the check the first and last index of the number in a flattened array, deciding whether or not it ought to be added to the overall sum:

let sum = 0;
const numbers = data.flat(Infinity);

for ( let i = 0; i < numbers.length; i   ) {
    const first = numbers.indexOf( numbers[ i ] );
    const last = numbers.lastIndexOf( numbers[ i ] );
    if ( i == first && i != last ) {
        sum = sum   numbers[ i ];
    }
}

// Sum of numbers in set
console.log( sum );