Find a pair of elements from an array whose sum equals a given number

Question

Given array of n integers and given a number X  find all the unique pairs of elements  a b   whose summation is equal to X   The following is my solution  it is O nLog n  n   but I am not sure whether or not it is optimal     int main void        int arr  10     1 2 3 4 5 6 7 8 9 0       findpair arr  10  7     void findpair int arr    int len  int sum        std  sort arr  arr len       int i   0      int j   len -1      while  i  lt  j           while  arr i    arr j    lt   sum  amp  amp  i  lt  j                        if  arr i    arr j      sum                  cout  lt  lt       lt  lt  arr i   lt  lt       lt  lt  arr j   lt  lt       lt  lt  endl              i                      j--          while  arr i    arr j    gt   sum  amp  amp  i  lt  j                        if  arr i    arr j      sum                  cout  lt  lt       lt  lt  arr i   lt  lt       lt  lt  arr j   lt  lt       lt  lt  endl              j--

User · Answer

This prints the pairs and avoids duplicates using bitwise manipulation   public static void findSumHashMap int   arr  int key        Map lt Integer  Integer gt  valMap   new HashMap lt Integer  Integer gt         for int i 0 i lt arr length i            valMap put arr i   i        int indicesVisited   0       for int i 0 i lt arr length i              if valMap containsKey key - arr i    amp  amp  valMap get key - arr i      i                if    indicesVisited  amp    1 lt  lt i     1 lt  lt valMap get key - arr i       gt  0                     int diff   key-arr i                   System out println arr i         diff                   indicesVisited   indicesVisited    1 lt  lt i     1 lt  lt valMap get key - arr i

User · Answer

less than o n  solution will be    function array k            var map                 for element in array              map element    true               if map k-element                     return  k element

User · Answer

Here is Java code for three approaches  1  Using Map O n   HashSet can also be used here   2  Sort array and then use BinarySearch to look for complement O nLog n   3  Traditional BruteForce two loops O n 2     public class PairsEqualToSum    public static void main String   args        int a      1 10 5 8 2 12 6 4       findPairs1 a 10       findPairs2 a 10       findPairs3 a 10          Method1 - O N  use a Map to insert values as keys  amp  check for number s complement in map     static void findPairs1 int  a  int sum           Map lt Integer  Integer gt  pairs   new HashMap lt Integer  Integer gt             for int i 0  i lt a length  i                 if pairs containsKey sum-a i                    System out println     a i       sum-a i                     else                pairs put a i   0                        Method2 - O nlog n   using Sort static void findPairs2 int  a  int sum           Arrays sort a           for int i 0  i lt a length 2  i                 int complement   sum - a i               int foundAtIndex   Arrays binarySearch a complement               if foundAtIndex  gt 0  amp  amp  foundAtIndex    i    to avoid situation where binarySearch would find the original and not the complement like  5                  System out println     a i       sum-a i                         Method 3 - Brute Force O n 2  static void findPairs3 int  a  int sum        for int i 0  i lt a length  i             for int j i  j lt a length j                 if a i  a j     sum                  System out println     a i      a j

User · Answer

In python  arr    1  2  4  6  10  diff hash      expected sum   3 for i in arr      if diff hash has key i           print i  diff hash i      key   expected sum - i     diff hash key    i

User · Answer

Implementation in Java   Using codaddict s algorithm  Maybe slightly different   import java util HashMap   public class ArrayPairSum     public static void main String   args                 int   a    2 45 7 3 5 1 8 9       printSumPairs a 10                public static void printSumPairs int   input  int k       Map lt Integer  Integer gt  pairs   new HashMap lt Integer  Integer gt          for int i 0 i lt input length i              if pairs containsKey input i                System out println input i         pairs get input i             else             pairs put k-input i   input i                 For input    2 45 7 3 5 1 8 9  and if Sum is 10  Output pairs    3 7  8 2 9 1   Some notes about the solution     We iterate only once through the array --  O n  time Insertion and lookup time in Hash is O 1   Overall time is O n   although it uses extra space in terms of hash

User · Answer

C  11  run time complexity O n     include  lt vector gt   include  lt unordered map gt   include  lt utility gt   std  vector lt std  pair lt int  int gt  gt  FindPairsForSum          const std  vector lt int gt  amp  data  const int amp  sum        std  unordered map lt int  size t gt  umap      std  vector lt std  pair lt int  int gt  gt  result      for  size t i   0  i  lt  data size      i                if  0  lt  umap count sum - data i                          size t j   umap sum - data i                result push back  data i   data j                       else                       umap data i     i                       return result

User · Answer

My Solution - Java - Without duplicates      public static void printAllPairSum int   a  int x       System out printf  printAllPairSum  s  d  n   Arrays toString a  x       if a  null  a length  0           return            int length   a length      Map lt Integer Integer gt  reverseMapOfArray   new HashMap lt  gt  length 1 0f       for  int i   0  i  lt  length  i              reverseMapOfArray put a i   i              for  int i   0  i  lt  length  i              Integer j   reverseMapOfArray get x - a i            if j  null  amp  amp  i lt j               System out printf  a  d    a  d     d    d    d n  i j a i  a j  x                       System out println  ------------------------------

User · Answer

in C            int   array   new int     1  5  7  2  9  8  4  3  6       given array         int sum   10     given sum         for  int i   0  i  lt   array Count   - 1  i                if  array Contains sum - array i                    Console WriteLine   0    1    array i   sum - array i

User · Answer

Just attended this question on HackerRank and here s my  Objective C  Solution    - NSNumber  sum  NSArray   a andK  NSNumber  k       NSMutableDictionary  dict    NSMutableDictionary dictionary       long long count   0      for long i 0 i lt a count i              if dict a i                  count                NSLog   a i       dict array i         a i   dict a i                       else              NSNumber  calcNum     k longLongValue-  NSNumber  a i   longLongValue               dict calcNum    a i                        return   count       Hope it helps someone

User · Answer

Javascript solution   var sample input    0  1  100  99  0  10  90  30  55  33  55  75  50  51  49  50  51  49  51   var result   getNumbersOf 100  sample input  true        function getNumbersOf targetNum  numbers  unique  res        var number   numbers shift         if   numbers length            return res             for  var i   0  i  lt  numbers length  i              if   number   numbers i       targetNum                var result    number  numbers i                if  unique                  if  JSON stringify res  indexOf JSON stringify result    lt  0                    res push result                                                 else                 res push result                             numbers splice numbers indexOf numbers i    1               break                      return getNumbersOf targetNum  numbers  unique  res

User · Answer

Nice solution from Codeaddict   I took the liberty of implementing a version of it in Ruby   def find sum arr sum   result      h   Hash arr map   i   i i     arr each    l  result l    sum-l  if h sum-l   amp  amp   result sum-l      result end   To allow duplicate pairs  1 5    5 1  we just have to remove the   amp  amp   result sum-l  instruction

User · Answer

this is the implementation of O n lg n  using binary search implementation inside a loop    include  lt iostream gt   using namespace std   bool  inMemory    int pairSum int arr    int n  int k        int count   0       if n  0          return count      for  int i   0  i  lt  n    i                int start   0          int end   n-1                while start  lt   end                        int mid   start    end-start  2              if i    mid                  break              else if  arr i    arr mid      k  amp  amp   inMemory i   amp  amp   inMemory mid                                 count                    inMemory i    true                  inMemory mid    true                            else if arr i    arr mid   gt   k                                end   mid-1                            else                 start   mid 1                      return count      int main         int arr      1  2  3  4  5  6  7  8  9  10       inMemory   new bool 10       for  int i   0  i  lt  10    i                inMemory i    false            cout  lt  lt  pairSum arr  10  11   lt  lt  endl      return 0

User · Answer

Solution in java  You can add all the String elements to an ArrayList of strings and return the list  Here I am just printing it out   void numberPairsForSum int   array  int sum        HashSet lt Integer gt  set   new HashSet lt Integer gt         for  int num   array            if  set contains sum - num                 String s   num           sum - num      add up to     sum              System out println s                     set add num

User · Answer

A simple Java code snippet for printing the pairs below       public static void count all pairs with given sum int arr    int S           if arr length  lt  2           return                    HashSet values   new HashSet arr length       for int value   arr values add value       for int value   arr           int difference   S - value      if values contains difference   amp  amp  value lt difference           System out printf    d   d   n   value  difference

User · Answer

https   github com clockzhong findSumPairNumber  I did it under O m n  complexity cost for both time and memory space  I suspect that s the best algorithm so far

User · Answer

Here is a solution witch takes into account duplicate entries  It is written in javascript and assumes array is sorted   The solution runs in O n  time and does not use any extra memory aside from variable   var count pairs   function  arr x      if  x  x   0    var pairs   0    var i   0    var k    arr length-1    if  k 1  lt 2  return pairs    var halfX   x 2     while i lt k        var curK    arr k       var curI    arr i       var pairsThisLoop   0      if curK curI  x             if midpoint and equal find combinations       if curK  curI            var comb   1          while --k gt  i  pairs   comb             break                   count pair and k duplicates       pairsThisLoop          while  arr --k   curK  pairsThisLoop             add k side pairs to running total for every i side pair found       pairs  pairsThisLoop        while  arr   i   curI  pairs  pairsThisLoop        else            if we are at a mid point       if curK  curI  break        var distK   Math abs halfX-curK         var distI   Math abs halfX-curI         if distI  gt  distK  while  arr   i   curI         else while  arr --k   curK               return pairs      I solved this during an interview for a large corporation   They took it but not me  So here it is for everyone   Start at both side of the array and slowly work your way inwards making sure to count duplicates if they exist   It only counts pairs but can be reworked to   find the pairs      find pairs  lt  x     find pairs   x   Enjoy

User · Answer

I bypassed the bit manuplation and just compared the index values   This is less than the loop iteration value  i in this case   This will not print the duplicate pairs and duplicate array elements also   public static void findSumHashMap int   arr  int key        Map lt Integer  Integer gt  valMap   new HashMap lt Integer  Integer gt         for  int i   0  i  lt  arr length  i              valMap put arr i   i             for  int i   0  i  lt  arr length  i              if  valMap containsKey key - arr i                    amp  amp  valMap get key - arr i      i                if  valMap get key - arr i    lt  i                    int diff   key - arr i                   System out println arr i          diff

User · Answer

O n   def find pairs L sum       s   set L      edgeCase   sum 2     if L count edgeCase    2          print edgeCase  edgeCase     s remove edgeCase            for i in s          diff   sum-i         if diff in s               print i  diff   L    2 45 7 3 5 1 8 9  sum   10           find pairs L sum    Methodology  a   b   c  so instead of looking for  a b  we look for a   c -  b

User · Answer

Implementation in Java   Using codaddict s algorithm   import java util Hashtable  public class Range    public static void main String   args           TODO Auto-generated method stub     Hashtable mapping   new Hashtable        int a     80 79 82 81 84 83 85       int k   160       for  int i 0  i  lt  a length  i             mapping put a i   i              for  int i 0  i  lt  a length  i             if  mapping containsKey k - a i    amp  amp   Integer mapping get k-a i      i               System out println k-a i        a i                                  Output   81  79 79  81   If you want duplicate pairs  eg  80 80  also then just remove  amp  amp   Integer mapping get k-a i      i from the if condition and you are good to go

User · Answer

public static int   f  final int   nums  int target        int   r   new int 2       r 0    -1      r 1    -1      int   vIndex   new int 0Xfff       for  int i   0  i  lt  nums length  i              int delta   0Xff          int gapIndex   target - nums i    delta          if  vIndex gapIndex     0                r 0    vIndex gapIndex               r 1    i   1              return r            else               vIndex nums i    delta    i   1                      return r

User · Answer

One Solution can be this  but not optimul  The complexity of this code is O n 2     public class FindPairsEqualToSum    private static int inputSum   0   public static List lt String gt  findPairsForSum int   inputArray  int sum        List lt String gt  list   new ArrayList lt String gt         List lt Integer gt  inputList   new ArrayList lt Integer gt         for  int i   inputArray            inputList add i             for  int i   inputArray            int tempInt   sum - i          if  inputList contains tempInt                 String pair   String valueOf i          tempInt               list add pair                       return list

User · Answer

A Simple program in java for arrays having unique elements   import java util    public class ArrayPairSum       public static void main String   args             int   a    2 4 7 3 5 1 8 9 5           sumPairs a 10                public static void sumPairs int   input  int k         Set lt Integer gt  set   new HashSet lt Integer gt               for int i 0 i lt input length i              if set contains input i                System out println input i         k-input i             else             set add k-input i

User · Answer

int    arr    1 2 3 4 5 6 7 8 9 0    var z    from a in arr      from b in arr      where 10 - a    b      select new   a  b    ToList

User · Answer

Another solution in Swift  the idea is to create an hash that store values of  sum - currentValue  and compare this to the current value of the loop  The complexity is O n    func findPair list   Int     sum  Int  - gt    Int  Int          var hash   Set lt Int gt      save list of value of sum - item      var dictCount    Int  Int      to avoid the case A 2   sum where we have only one A in the array     var foundKeys    Set lt Int gt      to avoid duplicated pair in the result       var result     Int  Int       this is for the result      for item in list              keep track of count of each element to avoid problem   2  3  5   10 - gt  result    5 5          if   dictCount keys contains item                 dictCount item    1           else               dictCount item    dictCount item     1                      if my hash does not contain the  sum - item  value - gt  insert to hash          if  hash contains sum-item                hash insert sum-item                       check if current item is the same as another hash value or not  if yes  return the tuple          if hash contains item   amp  amp               dictCount item   gt  1    sum    item 2     check if we have item 2   sum or not                        if  foundKeys contains item   amp  amp   foundKeys contains sum-item                    foundKeys insert item    add to found items in order to not to add duplicated pair                  result append  item  sum-item                                     return result      test  let a   findPair  2 3 5 4 1 7 6 8 9 5 3 3 3 3 3 3 3 3 3   14    will return  8 6  and  9 5

User · Answer

Python Implementation       import itertools list    1  1  2  3  4  5   uniquelist   set list  targetsum   5 for n in itertools combinations uniquelist  2       if n 0    n 1     targetsum          print str n 0             str n 1     Output   1   4 2   3

User · Answer

I can do it in O n   Let me know when you want the answer  Note it involves simply traversing the array once with no sorting  etc    I should mention too that it exploits commutativity of addition and doesn t use hashes but wastes memory     using System  using System Collections Generic      An O n  approach exists by using a lookup table  The approach is to store the value in a  bin  that can easily be looked up e g   O 1   if it is a candidate for an appropriate sum   e g    for each a k  in the array we simply put the it in another array at the location x - a k    Suppose we have  0  1  5  3  6  9  8  7  and x   9  We create a new array   indexes     value  9 - 0   9     0 9 - 1   8     1 9 - 5   4     5 9 - 3   6     3 9 - 6   3     6 9 - 9   0     9 9 - 8   1     8 9 - 7   2     7   THEN the only values that matter are the ones who have an index into the new table   So  say when we reach 9 or equal we see if our new array has the index 9 - 9   0  Since it does we know that all the values it contains will add to 9   note in this cause it s obvious there is only 1 possible one but it might have multiple index values in it which we need to store    So effectively what we end up doing is only having to move through the array once  Because addition is commutative we will end up with all the possible results   For example  when we get to 6 we get the index into our new table as 9 - 6   3  Since the table contains that index value we know the values   This is essentially trading off speed for memory      namespace sum       class Program               static void Main string   args                        int num   25              int X   10              var arr   new List lt int gt                 for int i   0  i  lt   num  i    arr Add  new Random  int  DateTime Now Ticks   i num    Next 0  num 2                Console Write       for  int i   0  i  lt  num - 1  i    Console Write arr i           Console WriteLine arr arr Count-1       -     X               var arrbrute   new List lt Tuple lt int int gt  gt                 var arrfast   new List lt Tuple lt int int gt  gt                  for int i   0  i  lt  num  i                for int j   i 1  j  lt  num  j                    if  arr i    arr j     X                       arrbrute Add new Tuple lt int  int gt  arr i   arr j                     int M   500              var lookup   new List lt List lt int gt  gt                 for int i   0  i  lt  1000  i    lookup Add new List lt int gt                  for int i   0  i  lt  num  i                                             Check and see if we have any  matches                  if  lookup M   X - arr i   Count    0                                        foreach var j in lookup M   X - arr i                        arrfast Add new Tuple lt int  int gt  arr i   arr j                                         lookup M   arr i   Add i                               for int i   0  i  lt  arrbrute Count  i                    Console WriteLine arrbrute i  Item1           arrbrute i  Item2           X               Console WriteLine  ---------                for int i   0  i  lt  arrfast Count  i                    Console WriteLine arrfast i  Item1           arrfast i  Item2           X                Console ReadKey

User · Answer

There are 3 approaches to this solution   Let the sum be T and n be the size of array  Approach 1  The naive way to do this would be to check all combinations  n choose 2   This exhaustive search is O n2    Approach 2  nbsp    nbsp A better way would be to sort the array  nbsp This takes O n log n   Then for each x in array A   use binary search to look for T-x  This will take O nlogn   So  overall search is nbsp  O n log n   Approach 3    The best way  would be to insert every element into a hash table  without sorting   This takes O n  as constant time insertion  Then for every x   we can just look up its complement  T-x  which is O 1   Overall the run time of this approach is O n     You can refer more here Thanks

User · Answer

Let arr be the given array    And K be the give sum   for i 0 to arr length - 1 do     key is the element and value is its index    hash arr i     i   end-for  for i 0 to arr length - 1 do     if K-th element exists and it s different then we found a pair   if hash K - arr i      i       print  quot pair i   hash K - arr i   has sum K quot    end-if end-for

User · Answer

Solution in Python using list comprehension  f    i j  for i in list for j in list if j i  X     O N2   also gives two ordered pairs-  a b  and  b a  as well

User · Answer

A simple python version of the code that find a pair sum of zero and can be modify to find k   def sumToK lst       k   0     lt - define the k here     d        build a dictionary     build the hashmap key   val of lst  value   i for index  val in enumerate lst       d val    index    find the key  if a key is in the dict  and not the same index as the current key for i  val in enumerate lst       if  k-val  in d and d k-val     i          return True  return False   The run time complexity of the function is O n  and Space  O n  as well

[algorithm] Find a pair of elements from an array whose sum equals a given number

Examples related to algorithm