CareerCup

The solutions described here is O(n log n) due to sorting. There is an O(n) solution using a hashtable, therefore, this is an O(n) space solution:

1. Put numbers in the hashtable (this in O(n))
2. Iterate the array and subtract each element from sum and check if the result is in the hashtable.
2.a. if it's in the hashtable, print the two numbers
2.b. if it's not then continue

There is a special case though, when the array contains duplicates. In that case, you will also need to save the count of the number and process accordingly. e.g., if the array is [2,3,5,10] and sum = 6, 6-3=3 and 3 is in the hashtable, so you need to check if the count of the 3 in the hashtable is >=2.

Sort the array and start pointers from both ends of the array checking if the given pair add up to the given value.
0. If the current pair sum equals the value of the given number print the pair.
1. If the current pair sum exceeds the given number decrement the right pointer by 1
2. else increment the left pointer by 1

Here is one solution I came up with by Mathematica:

findPairs[lst_List, sum_] := 
 Select[Subsets[lst, {2}], Plus @@ # == sum &]

public static void main(String[] args) {
		int[] a = new int[] { 1, 3, 10, 4, 5, 6, 7, 2, 6 };
Set<String> resultSet = new HashSet<String>();
		int sum = 12;
		if (a == null || a.length < 2) {
			return;
		}

		int left = 0;
		int right = a.length - 1;
		java.util.Arrays.sort(a);
		while (left < right) {
			int i = a[left];
			int j = a[right];
			if (i + j == sum) {
				resultSet.add(String.valueOf(i)+"-"+String.valueOf(j));
				left++;
				right--;
			} else if (i + j > sum) {
				right--;
			} else {
				left++;
			}
		}
                System.out.println(resultSet);   
	}

Think we might miss the 6, 6 pair with the above approach.

You can solve it like:
a.First sort the array in non-decreasing order.Take two pointers left and right.Left point to the start and the right pointer points to the end of the array.
b.while(left<right)
b.check whether a[left]+a[right]<k.If yes then increment the left pointer by one.
c.check whether a[left]+a[right]>k.If yes decrement the right pointer by one.
d.If a[left]+a[right]==k.Return true

public class CheckSum {

/**
* @param args
*/
public static void main(String[] args) {
int a[]={4,5,1,3,2};int c[]=new int[2];int j=0;
for(int i=0;i<a.length;i++)
{j=1;

while(j<5)
{System.out.println("j"+j);
if(a[i]+a[j]==6)
{System.out.println("good"+"\n");
for(int t=0;t<2;t++)
{
//int b[]=new int[t];
c[0]=a[i];
//t--;
c[1]=a[j];
System.out.println(c[t]);
}

}
j++;
}
}


}

}

A sorting based solution O(nlogn). If the array was pre-sorted, this solution will take O(n).

Sharing the code on CodeBunk so you can run it.

codebunk.com/bunk#-Ix36lc9A5HABZn1fCe9

O(n) time & space, as simple/short as possible

public static List<Integer[]> compute(List<Integer> ints, int sum){
		Set<Integer> intsNeeded = new HashSet<Integer>();
		List<Integer[]> answer = new ArrayList<Integer[]>();
		
		for(Integer num : ints){
			if(intsNeeded.contains(num))
				answer.add(new Integer[]{num, sum - num});
			else
				intsNeeded.add(sum-num);
		}
		return answer;
	}

def sumupto(inp, s):
  a = {}
  res = []
  for i in inp:
    if i in a:
      res.append((a[i], i))
    else:
      a[s-i] = i
  return res

What about 1,2,3 which also sums upto 6

What about doing bit masking and chcking set bits if they add upto required sum.

public static void main(String[] args) {

int[] testArray = { 4, 5, 1, 2, 3};
int length = testArray.length-1;
int sol;
int sağ;
for (sol = 0; sol < length; sol++) {
for (sağ = length; sağ >=0 ; sağ--) {
if(sol>=sağ)
{break;}
if ((testArray[sol] + testArray[sağ]) == 6) {

System.out.println(testArray[sol] + "," + testArray[sağ]);
}
}
}
}

}

public class Sum1
{

/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
// EBAY.com

// Given an integer array, find pairs in an array which sum up to a given number.
// For example: Array{4,5,1,3,2} and required sum=6 then output should be [1,5] and [2,4].

int [] arr = {4,5, 1, 3, 2};
int sum = 6;

for(int i =0;i<arr.length;i++)
{
for (int j = i+1;j<arr.length;j++)
{
if ((arr[i] +arr[j])==sum)
{
System.out.println(arr[i]);
System.out.println(arr[j]);
System.out.println();
System.out.println();
}
}
}














}

}

int[] num={4,5,1,3,2,3};
int sum = 6;
int length=num.length;
HashSet<Integer> temp=new HashSet<Integer>();
for(int i=0;i<length;i++){
temp.add(num[i]);
}
for(int i=0;i<length;i++){
int tempSum=sum-num[i];
if(tempSum!=num[i]){
if(temp.contains(tempSum)){
System.out.println("numbers are: "+tempSum+", "+num[i]);
}
}else if(tempSum==num[i]){
int count =0;
for(int j=0;j<length;j++){
if(tempSum==num[j]){
count++;
}
}
if(count>=2){
System.out.println("numbers are: "+tempSum+", "+num[i]);
}
}
}

public class subSet
{
public Object a;
public int n;
public int[] x;
public boolean flag;
private int c;

public subSet(int[] a, int c)
{
this.a = a;
this.c = c;
this.n = a.length;
this.flag = false;
this.x = new int[n];
}

public boolean isPartial(int k)
{
int sum = 0;

for (int i = 0; i < k; i++)
sum += ((int[]) (a))[i] * x[i];
return sum <= c;
}

public boolean isComplete(int k)
{
int sum = 0;

if (k >= n)
{
for (int i = 0; i < n; i++)
sum += ((int[]) (a))[i] * x[i];
}
return sum == c;
}

public void printSolution(int k)
{
for (int i = 0; i < n; i++)
if (x[i] == 1)
System.out.print(((int[]) (a))[i] + " ");
System.out.println();
}

public static void backtrack(subSet p)
{
explore(p, 0);
if (!p.flag)
System.out.println("no sulution!");
}

private static void explore(subSet p, int k)
{
if (k >= p.n)
{
if (p.isComplete(k))
{
p.flag = true;
p.printSolution(k);
}
return;
}
for (int i = 0; i < 2; i++)
{
p.x[k] = i;
if (p.isPartial(k))
explore(p, k + 1);
}
}
public static void main(String args[])
{

int b[] = { 1, 2, 3, 4 };
subSet t = new subSet(b, 6);
t.backtrack(t);

}

}

public class subSet
{
	public Object a;
	public int n;
	public int[] x;
	public boolean flag;
	private int c;

	public subSet(int[] a, int c)
	{
		this.a = a;
		this.c = c;
		this.n = a.length;
		this.flag = false;
		this.x = new int[n];
	}

	public boolean isPartial(int k)
	{
		int sum = 0;
		
		for (int i = 0; i < k; i++)
			sum += ((int[]) (a))[i] * x[i];
		return sum <= c;
	}

	public boolean isComplete(int k)
	{
		int sum = 0;
		
		if (k >= n)
		{
			for (int i = 0; i < n; i++)
				sum += ((int[]) (a))[i] * x[i];
		}
		return sum == c;
	}

	public void printSolution(int k)
	{
		for (int i = 0; i < n; i++)
			if (x[i] == 1)
				System.out.print(((int[]) (a))[i] + " ");
		System.out.println();
	}

	public static void backtrack(subSet p)
	{
		explore(p, 0);
		if (!p.flag)
			System.out.println("no sulution!");
	}

	private static void explore(subSet p, int k)
	{
		if (k >= p.n)
		{
			if (p.isComplete(k))
			{
				p.flag = true;
				p.printSolution(k);
			}
			return;
		}
		for (int i = 0; i < 2; i++)
		{
			p.x[k] = i;
			if (p.isPartial(k))
				explore(p, k + 1);
		}
	}
	public static void main(String args[])
	{

		int b[] = { 1, 2, 3, 4 };
		subSet t = new subSet(b, 6);
		t.backtrack(t);

	}

}

import java.io.*;
class ArrTest1{
public static void main(String args[])throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int s;
System.out.println("Enter the size for array");
s=Integer.parseInt(br.readLine());
System.out.println("Enter the sum numbers equals to");
int d=Integer.parseInt(br.readLine());
int a[]=new int[s];
System.out.println("Enter the"+s +"numbers for array");

for(int i=0;i<s;i++){
a[i]=Integer.parseInt(br.readLine());
}
boolean b=true;
for(int i=s-1;i>=0;i--){
for(int j=i-1;j>=0;j--){
if(i==j){}
else{
if(a[i]+a[j]==d){
System.out.println("["+a[i]+"+"+a[j]+"]");
b=false;
}
}
}
}
if(b){
System.out.println("No pair found");
}
}
}

its very easy

O(nlog(n)) due to sorting...

public void findPairs(int[] array, int sum){
        Arrays.sort(array);
        int head = 0, tail=array.length - 1;
        while(head<=tail){
            if(array[head] + array[tail] == sum){
                System.out.println(array[head] + "+" + array[tail]);
                head++;
                tail--;
            }else if(array[head] + array[tail] > sum){
                tail--;
            }else if(array[head] + array[tail] < sum){
                head++;
            }
        }
    }

//This Works for negative values also

Integer arr[] = {1,2,3,5,6,7,8,9,4,3,3,5,-1,-2};

//Convert the Array to List
List<Integer> list = Arrays.asList(arr);

int sum = 6;

//Take a Map and put the values with their count of occurrence
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < list.size(); i++) {
if(null != map.get(list.get(i))) {
int value = map.get(list.get(i));
map.put(list.get(i), ++value);
}
else {
map.put(list.get(i), 1);
}
}

//Take a Iterator of the List
Iterator<Integer> it = list.iterator();

//Iterate the List
while (it.hasNext()) {
int val = it.next();
int remainVal = sum - val;

//Compare remain value of list with map
if(map.containsKey(remainVal) && map.get(val) < 2) {
System.out.println("Val1: "+val + "Val2: "+remainVal);
//Remove Values from the map so that no repetition is there
map.remove(remainVal);
map.remove(val);
}
if(map.containsKey(remainVal) && map.get(val) >= 2) {
System.out.println("Val11: "+val + "Val22: "+remainVal);
//Remove Values from the map so that no repetition is there
map.remove(remainVal);
map.remove(val);
}
}

#include <iostream>

using namespace std;

int main()
{
cout << "Hello World" << endl;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
int n=10;
int N=10;
int k=0;

for(int i =0; i< n; i++)
{

for(int j= i; j<n; j++)
{

if(a[i] + a[j] ==N)
{
cout<<a[i]<<endl;
cout<<a[j]<<endl;
cout<< " End Of Pair"<<endl;
}
}


}
return 0;
}

This problem can be phrased mathematically as:

x + y = z

where z = input
x, y are pairs from the array.

This equation can be modified to y = z - x

So if we take the input and subtract every value in the array then this will give us the set of candidates. Then the solution is to find all values in the candidates that are in the array.

You can do that by constructing a binary tree and then searching it. So the complexity of this algorithm would be O(nlogn).

Time: O(n)

static void pairEqualToSum()
	{
		System.out.println("----------------------------------------------------------------\n");

		int arr[]={4,5,1,3,2};
		int sum=6;

		Hashtable<Integer,Integer> h=new Hashtable();
		for(int i=0;i<arr.length;i++)
			h.put(arr[i],arr[i]);

		System.out.println(h.toString());

		int cur;
		for(int i=0;i<arr.length;i++)
		{
			cur=arr[i];
			if(h.containsKey(sum-cur) && cur!=h.get(sum-cur))
			{
				System.out.println(cur+" "+h.get(sum-cur));
				h.remove(sum-cur);
				h.remove(cur);
			}

		}
	}

public class Test {

	public static void main(String[] args) {

		 int arr[]={4,5,1,3,2};
		 for(int i=0;i<4;i++)
		 {
			 for(int j=i+1;j<5;j++){
				 if(arr[i]+arr[j]==6){
					 System.out.println("["+arr[i]+","+arr[j]+"]");
				 }
			 }
		 }
	}

}

public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}

Here's one solution I could think of:

public class hashM {
	public static void main(String[] args) {
		HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();

		hMap.put(1, 1);
		hMap.put(2, 3);
		hMap.put(3, 10);
		hMap.put(4, 4);
		hMap.put(5, 5);
		hMap.put(6, 6);
		hMap.put(7, 7);
		hMap.put(8, 2);
		hMap.put(9, 6);
		
		int sum = 12;
		for(int i=1; i<hMap.size(); i++) {
			int j=sum-hMap.get(i);
			
			if (hMap.containsValue(j)) {
				System.out.println("items: " + hMap.get(i) + "," + j);
			}
			j=0;
		}
	}

}

this will print the required output..

public static void main(String[] args) {

int[] testArray = { 4, 5, 1, 2, 3 };
int length = testArray.length;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (testArray[i] + testArray[j] == 6) {
System.out.println(testArray[i] + "," + testArray[j]);
}
}
}

}