Skip to content
Google Question
aneagoie
aneagoie
This Repl has no description
14comments
FadyKirolos
FadyKirolos
3 days ago
carwy385
carwy385
2 weeks ago

import java.util.HashSet; import java.util.Set;

/****************************************************************************************************

  • @author
    caryd
  • Find the pair in the array that equals the sum given.
  • {1, 2, 3, 9} = 8
  • {1, 2, 4, 4} = 8;
  • The array is sorted in order
  • a number can appear in the array more than one time. See example 2
  • Return true or false. True if there is a pair = sum
  • Please understand I wrote the if else loops out for the ease of reading the code.

*************************************************************************************/

public class SumPair {

/*********************************************************************************************** * Brute Force/Naive. * The first thing that comes to mind. * Go through the array and try each number with the other numbers in the array. * Ie 1 + 2, 1+3, 1+9, 2+1, etc. * This is bad because the time complexity is O(n^2) *****************************************************************************************/ public static boolean hasPairWithSum(int[] numbers, int sum) { for(int i:numbers) { for (int j:numbers){ if(i + j == sum) { return true; }else {} } } return false; } /****************************************************************************************************** * The Better solution * Arrays will not work as we can have duplicates of the same number in an array. * Hashtable, Hashmap, and map all have a key which we do not need the would add the the Big O for space. * Set/Hashset is the best option as it doesn't allow duplicates and it doesn't need a key. * The Big o will be O(n) ******************************************************************************************************/ public static boolean hasPairWithSum2(int[] numbers, int sum) { Set<Integer> comp = new HashSet<Integer>(); // I have shortened compliment to comp for code purposes. //Loop through he array and find the compliment for each number in the array. for(int i:numbers) { if(comp.contains(i)) { return true; }else{ comp.add(sum-i); } } return false; } /*************************************************************************************************** * Main method * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] numbers = {1, 2, 3, 9}; //int[] numbers = {1, 2, 4, 4}; int sum = 8; System.out.println( hasPairWithSum(numbers, sum)); System.out.println(hasPairWithSum2(numbers, sum)); }

}

IMTejesh95
IMTejesh95
3 weeks ago
import java.util.HashSet; import java.util.Set; /** * SumPair * find pair in array for provided sum * * Points: * 1. sorted array of numbers * 2. duplicate entries allowed * 3. return true/false */ public class SumPair { /* * Naive (First thing comes on mind) * Time Complexity: O(n^2) - not a good solution */ static boolean hasSumWithPair(int[] arr, int sum) { for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] + arr[j] == sum) return true; } } return false; } /* * Better solution * Questions: * 1. How large this input could be * Time Complexity: O(n) */ static boolean hasSumWithPairV2(int[] arr, int sum) { /* * Use appropriate data structure for storing the complements for num * - Array can have duplicate entries, not suitable * - Map is not suitable coz we won't be using key anywhere * - Set is a perfect, not duplicates, and not extra space for keys */ Set<Integer> complements = new HashSet<>(); /* * Loop through the array, check if set contains the number * if yes, this means there already a comlement present, return true * If not, add a complement in set */ for (int i = 0; i < arr.length; i++) { if (complements.contains(arr[i])) return true; complements.add(sum - arr[i]); } return false; } public static void main(String[] args) { int[] arr = { 1, 2, 5, 6, 8 }; int sum = 15; System.out.println(hasSumWithPairV2(arr, sum)); } }
GauravSukhatme
GauravSukhatme
4 weeks ago
def sum_to_num_c(array, sum): map = set() for i in range(0, len(array)): comp = abs(sum-array[i]) if(comp in map): return True map.add(array[i]) return False
dtoch123
dtoch123
3 months ago

Is it just me or does the naive solution not actually work? In trying to do a simple log, it's only iterating one time in the outer for loop.

NeilGirardi
NeilGirardi
4 months ago

I'm probably confused but shouldn't we be looking for sum - arr[i] in the source array and not the set? Of course it will be in the set on the second iteration of the loop because we put it there on line 22.

This is how I solved it:

const hasPairWithSum2 = (nums, sum) => { for (let i = 0; i < nums.length; i++) { const complementValue = sum - nums[i] let index = nums.indexOf(complementValue) // Does the nums array include the complement integer? // If the current value and the complement are the same number // do we have a pair? // For example, if sum is 8 and nums[i] === 4 do we have a second 4? if (index !== -1 && index !== i) { return true } } return false }
HimanshuMathur
HimanshuMathur
4 months ago

function hasPairWithSum(arr, sum){ const mySet = new Set(); const len = arr.length; pairs = [] for (let i = 0; i < len; i++){ if (mySet.has(arr[i])) { // 3,5 pairs.push([sum-arr[i],arr[i]]) } mySet.add(sum - arr[i]); } return pairs.length>0?pairs:false; }

console.log(hasPairWithSum([6,4,3,2,1,7], 9))

#this is how you can get pairs as well instead of just boolean

ZunnorainShah
ZunnorainShah
8 months ago

can someone provide the java code for this

jdavault
jdavault
10 months ago

I also like using the foreach ...over for i

function hasPairWithSum(array, targetSum) { const numSeen = new Set(); for (num of array) { if (numSeen.has(targetSum - num)) return [targetSum - num, num] //true numSeen.add(num) } return [] //false }

jdavault
jdavault
10 months ago

Here is a js version of what the google guy talked about with the "cutting the problem in half" .. O(LogN)

function hasPairWithSumBest(array, targetSum) { //array.sort((a, b) => a - b) // list is already sorted but if it wasn't you could sort it first let left = 0 let right = array.length - 1 while (left < right) { let currSum = array[left] + array[right] if (currSum === targetSum) { return true // or the values [array[left], array[right]] } else if (currSum < targetSum) { left++ } else if (currSum > targetSum) right-- } return false // or the value [] }