CareerCup

Sort the array

Two pointer - one to the begining and the other to the end of the array.

Compare the values pointed by the pointers untill the pointers collide
If the sum is lesser than m then increment the left pointer by one
If the sum is greater than m then decrement the right pointer by one
If the sum is equal to m then return "YES"

For all the geniuses who were happy with hash table and two pointer soln. THINK TWICE....

i/p array => 2,2,2
sum => 4

By Hash method you say 2 pairs, ACTUAL ANSWER 3 pairs [0,1][1,2] [0,2]

PLEASE POST A NEW ANSWER....:)

Ask the interviewer if the values are in a particular range say 1-n. If yes, use an array of size n to implement a simple hash and u can have the solution in O(n);

Also we can improve the solution given by KB, you need to check the who array if there are values in the array which are greater than m then we can simply disregard that part of the array. This is worthwhile if we know that the range is random and that there could be a lot of values which are greater than m. We can find the point till which to use the array using binary search.

Thought that I would take a shot at hash version.
I am simplified the sample a bit, but it seems to be working fine !
any comments is welcomed !

int main()
{
int arr[10]={5,7,1,2,3,4,6,8};
int count = 8;
int sum = 10;
int hash[10];
int i=0;
// generate hash range 1-10
for(i=0;i <10;i++)
hash[i] = 0;

for(i=0; i< count; i++)
hash[arr[i]] = 1;

for(i=0; i<= sum/2; i++)
if(hash[i])
if(hash[sum-i])
printf("\nFound %d-%d ", i, sum-i);

return(0);
}

my 2 cents ...

Rakesh , You could keep a running check instead of computing the entire hash table initially.

while (i<10) {if (hash[sum - arr[i]] > 0) return 1;   
              else hash[arr[i]]++ ;

And your code wont work for some cases say, int arr[10] = {5,0,0,...}. Also what if I give a value in the arr equal to 11. Hash out of bounds. Please check your code before submitting.

I would sort the array first. Then I would have one pointer at the start of the array (the smallest element) and one at the end of the array (the largest element)If the sum of the two integers is less than the required sum, you can get rid of the the first array element because it will be too small to add up to the sum with any of the other array elements. If the sum is too big, you can get rid of the last array element. If the sum matches the sum you are trying to acheive, store the two integers in the seperate data structure. Assuming there are no repeats in the array, you can now get rid of both the first and last element in the array. Keep working your way in from both ends of the array until you reach the center. Once the sort is done, the finding of pairs would be done in O(n) time.

If there are repeats in the array, you would have to do an extra check before you get rid of elements from the array, but otherwise it would be similar.

cant we do ti this way?

S=sum
for ( i =0;i<size of array,i++)
{
k=Array[i]
T=S-K
if(Binary search(T,Array))
if(pair(K,T) not in the datastructure)
enter pair(K,T) in datastructure

}

Create a bit stream of length= largest element
This would take O(n).
Now for each element in the array
y = sum-element.
check if yth bit in the bit stream is true
then print the element
else
set i th bit = true where i = value of the element.

this would take O(n).

--Tara
set the bit no. = value of the element as true.

One more solution to this problem.
suppose there are two no. a and b whose sum = a+b.
For a given sum if a> (a+b)/2 then b<(a+b)/2.
You can prove this inequality easily.
Now there are three kind of numbers.
<(a+b)/2 | >=(a+b)/2 | >(a+b)

if A[i]< (a+b)/2 then paired number A[j]>(a+b)/2 and a[j] can't fall into >(a+b).
suppose there are l number < (a+b)/2, m numbers >= (a+b)/2 and n numbers are >(a+b).

Assuming no space constraints.
create another array with the above conditions.
that will take O(l+m+n) time.
sort elements < (a+b)/2 --- O(l.log(l))
sort numbers > (a+b)/2 but < (a+b)/2---O(m.log(m)).

now keep two indices i and j
for( i=0,j=l+m;i<l && j>l;)
if(A[i]+A[j]>a+b) j--;
else if(A[i]+A[j]<a+b) i++;
else
print A[i], A[j];
this will take
O(l+m);

total complexity = O(l+m+n) + O(l.log(l)) + O(m.log(m)) + O(l+m);

Analysis of algo.
case 1. l~m and n<<l,m;
complexity = O(2l) + 2O(l.log(l)) + O(2l);
~ O(l.log(l))
or in general
O(nlogn).

yup....I think, hashing would me right thing to do:)

His can be done in O(n). Each time you look at the number "num" in the list, search the hash table to find sum - num. If its there, you found the pair. In any case, insert this number in the hash. By the time you complete the pass to the unsorted list, you will have all the pairs. This solution assumes that search/insert into hash table is O(1) in which case total complexity is O(n) since we are only doing one pass to the input list.

Simplest Solution:

Hash The Input Array...Ignore duplicates...

Take difference from first array and the sum for each element and store result in corresponding location in second array...
The Second array now has same number of elements as the first one..
Now Hash Elements from Second array.. if they collide then the index of this element from second array and same index from first array gives you the pair.

This will also consider GreatOnes Case and prints 3 pairs.

while inserting in hash, if u find a pair whose sum is equal to given sum,
then reverse the pair and insert it again into hashtable, to get exact no. of pairs..as said by THE GREAT ONE.

Here is my working code. Hope you guys like it :)

using System;
using System.Collections.Generic;
using System.Text;

namespace Careercup
{
class Arraysum
{
static void Main()
{
int[] arr = new int[] {1,2,3,2,5,4,1,7,3,9,10,12 };
int sum = Convert.ToInt32(Console.ReadLine()); //say 5
int tempsum = 0;
int i = 0, j = 0;
while (j < arr.Length)
{
tempsum += arr[j];
if (tempsum == sum)
{
Console.WriteLine("{0}, {1}",arr[i], arr[j]);
j = j + 1;
}
else if (tempsum < sum)
j = j + 1;
else if (tempsum > sum)
{
i = i + 1;
j = i;
tempsum = 0;
}
}
Console.Read();
}
}
}

Output:
2,3
3,2
4,1

Numbers in the array will act as keys and their index will act as values. So, if you have an array like 2,2,2 insert 2 the first element as (2,1). When adding second 2 check if it is there in the hashtable, if yes go to that location and update the value as (1,2) so now it will look like (2,(1,2)) and when third is added (2,(1,2,3)). So, if some number pair up with 2 then we can form 3 pairs with 2 at index 1,2 and 3.

3 Solutions

1. Everyone knows about the ineffecient O(n2) solution
2. Sort the numbers and keep two pointers one to the start and the other at the end and move them accordingly.
3. See the above post of using hash tables in O(n) time.

you can solve this by O(nlogn) time

1. sort
2. two pointer, one in front, one at end; then u know what to do

vector<list<int>> FindPair(int* array, int size, int sum)
{
//suppose the array has sorted already

vector<list<int>> r;
int j=size-1;
for(int i=0;i<size/2;i++)
{
if(sum-array==array[j])
{
list<int> temp=new list<int>();
temp.push_front(array[i]);
temp.push_front(array[size-i-1]);
r.push_back(temp);
}
else if(sum-array<array[size-i-1])
{
j--;
}
}
return r;

}

It takes O(nlgn) time and O(1) space

given: arr[0..n]
create a hash table with key = sum - arr[i] where i=0..n and value = arr[i].
then for each arr[i] check if its present in keys, if yes fetch the record print it.

if i am not wrong this solution handles duplicate, -ve, +ve in an array.

this function in c# can do the job
public void findPair(int valueToFind,int[] arrayToLook){
System.Collections.Hashtable a = new System.Collections.Hashtable();
for (int i = 0; i < arrayToLook.Length; i++)
{
a[arrayToLook[i]]=true;
}


System.Collections.ICollection cbase = ((System.Collections.Hashtable)a.Clone()).Keys;
foreach (int i in cbase)
{

if(a.Contains (valueToFind-i))
{
if ((bool)a[valueToFind - i])
{
Console.WriteLine("({0},{1})", i.ToString(), (valueToFind - i).ToString());
a[i]=false;
}
}
}
}

One simple O(n lg n ) algorithm -

for each number say k in the array, do a binary search for sum-k. Binary search will take lg n time and there will be n calls to binary search so n lg n

One simple O(n lg n ) algorithm -

for each number say k in the array, do a binary search for sum-k. Binary search will take lg n time and there will be n calls to binary search so n lg n

here is the solution:
interviewcodesnippets.com/?p=181

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

class Program
{
public void Numbers(int[] arr, int testNumber)
{
Hashtable ht = new Hashtable();

for (int i = 0; i < arr.Length; ++i)
{
int secondNumber = (testNumber - arr[i]);
if (!ht.ContainsKey(arr[i]))
{
if (ht.ContainsKey(secondNumber))
{
ht.Add(arr[i], secondNumber);
}
else
ht.Add(arr[i], ' ');
}

}
foreach (DictionaryEntry de in ht)
{
if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
{
Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);

}
}

}
static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
//the input number
int testNumber = 5;
Program p = new Program();
p.Numbers(arr, testNumber);
Console.ReadKey();

}
}

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

class Program
    {
        public void Numbers(int[] arr, int testNumber)
        {
            Hashtable ht = new Hashtable();
          
            for (int i = 0; i < arr.Length; ++i)
            {
                int secondNumber = (testNumber - arr[i]);
                if (!ht.ContainsKey(arr[i]))
                {
                    if (ht.ContainsKey(secondNumber))
                    {
                        ht.Add(arr[i], secondNumber);
                    }
                    else
                    ht.Add(arr[i], ' ');
                }
                              
            }
            foreach (DictionaryEntry de in ht)
            {
                if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
                {
                    Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);
                 
                }
            }
            
        }
        static void Main(string[] args)
        {
            int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
            //the input number
            int testNumber = 5;
            Program p = new Program();
            p.Numbers(arr, testNumber);
            Console.ReadKey();

        }
    }

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

class Program
    {
        public void Numbers(int[] arr, int testNumber)
        {
            Hashtable ht = new Hashtable();
          
            for (int i = 0; i < arr.Length; ++i)
            {
                int secondNumber = (testNumber - arr[i]);
                if (!ht.ContainsKey(arr[i]))
                {
                    if (ht.ContainsKey(secondNumber))
                    {
                        ht.Add(arr[i], secondNumber);
                    }
                    else
                    ht.Add(arr[i], ' ');
                }
                              
            }
            foreach (DictionaryEntry de in ht)
            {
                if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
                {
                    Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);
                 
                }
            }
            
        }
        static void Main(string[] args)
        {
            int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
            //the input number
            int testNumber = 5;
            Program p = new Program();
            p.Numbers(arr, testNumber);
            Console.ReadKey();

        }
    }

This program will print all such numbers without repetition.
o(n) is the time and space complexity. Please comment ..

class Program
    {
        public void Numbers(int[] arr, int testNumber)
        {
            Hashtable ht = new Hashtable();
          
            for (int i = 0; i < arr.Length; ++i)
            {
                int secondNumber = (testNumber - arr[i]);
                if (!ht.ContainsKey(arr[i]))
                {
                    if (ht.ContainsKey(secondNumber))
                    {
                        ht.Add(arr[i], secondNumber);
                    }
                    else
                    ht.Add(arr[i], ' ');
                }
                              
            }
            foreach (DictionaryEntry de in ht)
            {
                if ((Convert.ToInt32(de.Key) + Convert.ToInt32(de.Value) == testNumber))
                {
                    Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);
                 
                }
            }
            
        }
        static void Main(string[] args)
        {
            int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
            //the input number
            int testNumber = 5;
            Program p = new Program();
            p.Numbers(arr, testNumber);
            Console.ReadKey();

        }
    }

void sumCompare (int a[], int size)
{
int i = 0;
while (a[i] > 0 && i < size) {
int j = i;
while (a[j] > 0 && j < size) {
loop_count++;
if (a[i] + a[j] == 10) {
printf ("%d, %d\n", a[i], a[j]);
a[i] = -1;
a[j] = -1;
}
j++;
}
i++;
}
}

above solution works for all +ve num

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package findsumfromarray;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.Hashtable;

/**
 *
 * @author Sushant
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
        {
            int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };
            //the input number
            int testNumber = 5;
            Program p = new Program();
            p.Numbers(arr, testNumber);
           //console.ReadKey();

        }

}
class Program
    {
        public void Numbers(int[] arr, int testNumber)
        {
            int i = 0;
            Hashtable ht = new Hashtable();

            for (i = 0; i < arr.length; ++i)
            {
                int secondNumber = (testNumber - arr[i]);
                if (!ht.containsKey(arr[i]))
                {
                   if (!ht.containsKey(secondNumber))
                    {
                        ht.put(arr[i], secondNumber);
                    }
                    else
                    ht.put(arr[i], ' ');
                }
                //else
//                ht.put(arr[i], ' ');
                //System.out.println("Hastable list "+ht.get(arr[i]));
                
            }
            System.out.println("Hastable key " +ht.keySet());
            System.out.println("Get value at "+ht.get(9));
        }
}

The code works fine ..... Try running it ..

how about this soln..

public static void findPairEqualtoSum(Integer[] num, int sum){
List<Integer> numList = Arrays.asList(num);
List<Integer[]> numPair = new ArrayList<Integer[]>();

for(int i = 0;i<numList.size();i++){
if(numList.contains(numList.get(i)-sum)){
Integer[] temp = {numList.get(i), (numList.get(i)-sum)};
Integer[] temp1 = {(numList.get(i)-sum), numList.get(i)};
if(!numPair.contains(temp) ||!numPair.contains(temp1))
numPair.add(temp);
}

}

}

Write A program that takes an array with maximum 20 characters and find the product of the elements in array

class Program
{
public void Numbers(int[] arr, int testNumber)
{
for (int i = 0; i < arr.Length; ++i)
{
if (arr.Contains(testNumber - arr[i])
{
Console.WriteLine("(" + arr[i].ToString() + ", " + (sum - arr[i]).ToString() + ")");
}
}
}

static void Main(string[] args)
{
int[] arr = { 4,-4,9,2,1, -1, 2, 3, -6, 4, 6, 11,5,0,0,0 };

int testNumber = 5;

Program p = new Program();

p.Numbers(arr, testNumber);
}
}