Home > Mobile >  Find the sum pair of the elements inside the array?
Find the sum pair of the elements inside the array?

Time:01-03

Have the function ArrayChallenge(arr) take the array of integers stored in arr, and determine if any two numbers (excluding the first element) in the array can sum up to the first element in the array. For example: if arr is [7, 3, 5, 2, -4, 8, 11], then there are actually two pairs that sum to the number 7: [5, 2] and [-4, 11]. Your program should return all pairs, with the numbers separated by a comma, in the order the first number appears in the array. Pairs should be separated by a space. So for the example above, your program would return: 5,2 -4,11

If there are no two numbers that sum to the first element in the array, return -1

Input: [17, 4, 5, 6, 10, 11, 4, -3, -5, 3, 15, 2, 7]
Output: 6,11 10,7 15,2
Final Output: --6--,--1----1-- --1--0,7 --1----5--,2

Input: [7, 6, 4, 1, 7, -2, 3, 12]
Output: 6,1 4,3
Final Output: --6--,--1-- 4,3

My approach

 function ArrayChallenge(arr) { 

 var sum = []

 for (var i = 0; i < arr.length; i  ){
    for (var j = i   1; j < arr.length; j  ){
    if(arr.[i]   arr[j]=== )
    }
   }
   // code goes here  
   return arr; 

   }

     // keep this function call here 
    console.log(ArrayChallenge(readline()));

Can you please help me with this ?

CodePudding user response:

Logic

  • Loop through the array.
  • Start from index 1 to last node (except index 0) in the outer loop.
  • Srart from one node next to the outer loop in the inner loop.
  • Check the sum of both nodes.
  • If the sum value is same as the node at first index, push that to sum array in required format.
  • Check the length of sum array. If length > 0 the join sum array and return. Else return -1

Working Code

const input = [17, 4, 5, 6, 10, 11, 4, -3, -5, 3, 15, 2, 7];
const input2 = [7, 6, 4, 1, 7, -2, 3, 12];
const input3 = [37, 6, 4, 1, 7, -2, 3, 12];
function ArrayChallenge(arr) {
  var sum = []
  for (var i = 1; i < arr.length; i  ) {
    for (var j = i   1; j < arr.length; j  ) {
      if (arr[i]   arr[j] === arr[0]) {
        sum.push([arr[i], arr[j]].join());
      }
    }
  }
  return sum.length > 0 ? sum.join(" ") : -1;
}
console.log(ArrayChallenge(input));
console.log(ArrayChallenge(input2));
console.log(ArrayChallenge(input3));

CodePudding user response:

Your approach uses a O(n^2) level complexity. This can be solved using O(n) if you're willing so sacrifice a little on space complexity.

What you can do is :

  1. Make an empty object.
  2. store all values of the array (not the 0th element) in the object as key and add it's value as true.
  3. Loop the array (from 1st index). Take the value and subtract it from the 0th element. find this subtracted value from the object, If it does not return undefined, make a pair and save it.

One drawback of this method is, you'll find duplicate entries in the result. This Approach uses O(n) Time complexity and O(n) space complexity

function ArrayChallange(arr) { 

  let numObj = {}
  let i = 1
  let result = []
  let tempVal

  // Pushing all elements of arr (from index 1) inside numObj
  while(i<arr.length){
    numObj[arr[i]] = true
  }

  i = 1
  
  // Looping the array to find pairs 
  while(i < arr.length){
    tempVal = numObj[Math.abs(arr[0] - arr[i])]
    if(tempVal){
      result.push(arr[i].toString()  "," tempVal.toString())
    }
  }
  
  if(result.length !== 0)
    return result.join(" ")
  else
    return -1
}

CodePudding user response:

You could use a reducer followed by a forEach loop in order to push the pairs to an empty array, then join them at the end.

const ArrayChallenge = (nums) => {
  const pairs = []

  // Get the first and remove it from the array
  const first = nums.splice(0, 1)[0]

  nums.reduce((all, curr) => {
    all.forEach((a) => {
      // Check if we have a match
      if (curr   a === first) {
        // check if it's already in the array
        // we don't want duplicates
        if (pairs.indexOf(`${a},${curr}`) === -1 && pairs.indexOf(`${curr},${a}`) === -1) {
          // push the pair to the array separated by a space
          pairs.push(`${curr},${a}`)
        }
      }
    })

    return all
  }, nums) // we pass in nums as the starting point
  
  // If there are no pairs then return -1
  if (pairs.length === 0) {
    return -1
  } else {
    // Join the pairs together with a space
    const result = pairs.join(' ')
    // Replace each digit (\d) with hyphens before and after 
    const parsed = result.replace(/(\d)/g, '--$1--')

    return parsed
  }
}



const result1 = ArrayChallenge([17, 4, 5, 6, 10, 11, 4, -3, -5, 3, 15, 2, 7])
console.log(result1)
const result2 = ArrayChallenge([7, 6, 4, 1, 7, -2, 3, 12])
console.log(result2)

  • Related