CareerCup

You can do this in O(nlogn) time complexity.
First sort the elements [O(nlogn)]
now start from the very first element and binary search (sum-firstelement) in i+1 to n.can be done in logn
Do so for every other number.
Overall time comlexity is still O(nlogn)

Example:
a={3,2,5,1,8,0} sum to be want 8
Sorted array={0,1,2,3,5,8};
start with 0 and binary search (8-0=8) in i+1 to n
and then start with 1 binary search (8-7) in i+1 to n
and so on :)

Well, the question needs to be clarified a lot.
1. Are the elements given in the range? If yes, use look up table.
2. else, do sort the array in nlogn, remove duplicates & find the pairs by running the two pointers, low[=0] & high[=n-1].
3. Are the pairs {2,6} & {6,2} considered the same?

Below code is based on: 1 & 3

void findPair(int* a,int n,int k)
{
        int hash[10]={0},i;
        for(i=0;i<n;i++)
        {
                if(!hash[a[i]])
                {
                        if(hash[k-a[i]])
                                printf("%d %d\n",a[i],k-a[i]);
                        else
                                hash[a[i]]=1;
                }
        }
}

complete code here: ideone.com/17w1Z

import java.util.HashMap;

public class GetPairValue {

void findPair(int Sum)
{
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
int[] a={2,4,6,4,7};
for(int i=0;i<5;i++)
{
if(hm.get(a[i])==null)
{
hm.put(a[i], Sum-a[i]);
}
}
System.out.println(hm);
for(int i=0;i<5;i++)
{
if(hm.get(a[i])!=null && hm.get(hm.get(a[i]))!=null)
{
System.out.println("Pair Values are : "+a[i]+" "+hm.get(a[i]));
hm.remove(a[i]);
hm.remove(Sum-a[i]);
}
}
}

public static void main(String str[])
{
GetPairValue gpv=new GetPairValue();
gpv.findPair(8);
}
}

#include<stdio.h>
#include<stdlib.h>

int a[10];

void sum(int a[10], int i, int j, int n, int s)
{
     if(i == n)
         return;
     if(j == n)
          return sum(a, i+1, 0, n, s);
     if(s == a[i] + a[j] && i != j)
     {
          printf("\n\nPairs are {%d and %d}\n\n", a[i], a[j]);
          a[j] = -5000; //---- Just to avoid the repetative pairs. Example: (2,4) and (4, 2). 
          sum(a, i+1, 0, n, s);
     }
     else        
         sum(a, i, j+1, n, s);
}
          

int main()
{
    int i, n, s;
    printf("\nEnter the number of elements\n");
    scanf("%d", &n);
    printf("\nEnter the sum\n");
    scanf("%d", &s);
    printf("\nEnter the elements\n");
    for(i = 0; i < n; i++)
          scanf("%d", &a[i]);
          
    sum(a, 0, 1, n, s);
    system("pause");
    return 0;
}

int array[]={10,20,30,40,50,60,70,80};
	n=8;
	cout<<" \n\nEnter the value :";
	cin>>val;
	int flag=0;
	i=0,j=n-1;
	while(i<j)
	{
		if(array[i]+array[j]==val)
		{
			cout<<"\n"<<array[i]<<" + "<<array[j]<<" = "<<val;
			flag=1;
			i++;
			j--;
		}
		else if(array[i]+array[j]>val)
			j--;
		else
			i++;
	}
	if(flag==0)
			cout<<"\nNo such elements";

Are (2,6) and (6,2) different ?

by firoz

#include <iostream>
#include <map>
using namespace std;

int main ()
{
  int ar[10]={2,3,7,6,4,5,0,1,2,8};
  map<int,int> mymap;
  map<int,int>::iterator it;
for(int i=0;i<10;i++)
{
 int a = ar[i];
 mymap[a]=a;
}
  // show content:
  
  //12+25 = 37
  int sum = 4;
  for ( it=mymap.begin() ; it != mymap.end(); it++ )
   { 
   int x = sum-(*it).first;
   if(mymap[x])
   {cout << (*it).first << "and" << mymap[x] << endl; }
    }
  getchar();
  return 0;
}

#include <iostream>
using namespace std;
int main()
{
	int givenArray[] = {7,2,4,6,4,6,1};
	int answer = 8;
	int count=0;
	for(int i=0; i<7; i++)
	{
		for(int j=i+1; j<7; j++)
		{
			count++;
			if(givenArray[i]+givenArray[j] == answer)
				cout<<"{"<<givenArray[i]<<","<<givenArray[j]<<"} => index("<<i<<" ,"<<j<<")"<<endl;
		}
	}
	cout<<"count = "<<count;
	return 0;
}

Array.prototype.unique = function(){
   var arr = this, new_arr = [];
   console.log(arr)
    for(var i=0 ; i<arr.length; i++){
        if(new_arr.indexOf(arr[i])===-1){
           new_arr.push(arr[i]);
        }
    }
   return new_arr;
}

function pair(array/*array*/,sum/*int*/){
    var result = {}, i=0, temp;
    /*preprocessing*/
    array = array.unique();
    console.log(array)
    while(i<array.length){
           temp = sum - parseInt(array[i]);
        if(array.slice(i).indexOf(temp)!=-1){
           result[array[i]] = temp;
        }
        i++;
    }
    
    return result;
}
    
    
    var array = [2,4,6,4,3,6,7,9,4,8,2,7,1];
    var sum = 10;
    
    var obj = pair(array,sum);
    for(var i in obj){
        document.write(i+" : "+obj[i]+"<br/>");

}

def get_pairs(l, n):
    l = sorted(l)
    i = 0
    j = len(l)-1
    while i < j:
        if l[i] + l[j] < n:
            ii = i
            while i < j and l[ii] == l[i]: i+=1
        elif l[i] + l[j] > n:
            jj = j
            while j > i and l[jj] == l[j]: j-=1
        else:
            print l[i], " ", l[j]
            while i+1 < j and l[i+1] == l[i]: i+=1
            i += 1
~

def find_unique_pairs(array, S): 
    values = set(array)
    result = set()
    for value in values:
        pair = S - value
        if pair in values and pair not in result:
            result.add(value)

    return [(value, S - value) for value in result]

print find_unique_pairs([2, 4, 6, 4, 6], 8)

It's easy to achieve O(n) by using Hash table. Travel the array from a1 to an, find whether there is sum-ai in Hash table. Then, put each element in Hash table if and only if it is not in hash table, unless the value is equal to sum/2.

HashMap approach. The only "cool" thing is I didn't use extra data structure to prevent from printing duplicate pairs. The embedded comment should be clear on how I am using the hashmap alone to prevent printing duplicate pairs.

static void findPairs(int[] arr, int sum) {
  HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
  for(int i : arr) {
    int j = sum-i;
    // suppose sum=8 and i=6, then j=2
    // we want to check whether j=2 is already in the map and whether
    // the value is false (indicating we haven't printed it yet)
    // furthermore, we want to check whether i=6 is in the map because
    // if so, then this pair must have been printed as well
    // exception is when i=j, such as i=4 and j=4
    if(map.containsKey(j) && !map.get(j)) {
      if(i == j || !map.containsKey(i)) {
        System.out.println("" + j + "+" + i);
        map.put(i, true);
        map.put(j, true);
      }
    } else {
      map.put(i, false);
    }
  }
}

Time: O(n), Space: O(n)

public class DistinctPairs {
    public static void main(String[] args) {
        System.out.println(count(10, 1, 2, 3, 6, 7, 8, 9, 1) == 3);
        System.out.println(count(47, 6, 1, 3, 46, 1, 3, 9) == 1);
        System.out.println(count(9, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
        System.out.println(count(9, 3, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
        System.out.println(count(6, 1, 5, 7, -1) == 2);
        System.out.println(count(6, 1, 5, 7, -1, 5) == 2);
        System.out.println(count(2, 1, 1, 1, 1) == 1);
    }

    private static int count(int target, int... arr) {
        int count = 0;
        Set<String> seen = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            int k = target - arr[i];
            int[] pair = new int[]{k, arr[i]};
            Arrays.sort(pair);
            String s = Arrays.toString(pair);
            if (set.contains(k) && !seen.contains(s)) {
                count++;
                seen.add(s);
            } else {
                set.add(arr[i]);
            }
        }
        return count;
    }
}

function my_sum()
{



}