CareerCup

The question is similar to find pairs that sum up to a given number. This problem can be solved in O(n) as:

#include <stdio.h>
#include <conio.h>

void findPairs(int arr[],int n,int sum)
{
	int temp,bin[1000]={0},i;
	for(i=0;i<n;i++)
	{
		temp=sum-arr[i];
		if(temp>=0&&bin[temp]==1)
		{
			printf(" %d %d ",temp,arr[i]);
		}
		bin[arr[i]]=1;
	}
}
int main()
{
	int arr[]={0,1,2,3,5,6,9};
	int n=sizeof(arr)/sizeof(arr[0]);
	findPairs(arr,n,9);
}

it is a typical question
1. sort the array in ascending order
2. set two pointer i,j:
i point at the first element(also smallest) of the array
j point at the last element(also largest) of the array
3. now move the i to the end of the array and move the j to the begin of the array according to the result r=array[i]+array[j]:
if r>target: set j--
if r<target: set i++
if r == target: you got one pair, if any number can only in one pair you should do both j-- and i++ otherwise its up to you choice

I always disagree with solutions coming out of naive iterations !!!

This can be solved by using Binary Search.
Perform a binary search for SUM - arr[i] in array.

This problem can be solved in three ways:
1)fix one element and find other element such that a[i] + a[j] =9 using linear search;
for(i=1;i<n;i++)
{ for (j= i;j<n; j++)
if(a[i] + a[j]==9)
return(i,j);
}
time complexity= O(n2)

2) fix first element and find other by binary search
for(i=1;i<n;i++)
{ use binary search here.
}
time complexity= O(nlogn)


3)
use greedy technique

take two pointers p1,p2 put them at rear ends.
then
if(a[p1] + a[p2] =9 )
return element at address;
otherwise
if(a[p1] +a[p2]> 9)
p2--;
elseif(a[p1] +a[p2]<9)
p1++;
time complexity= O(n)

1. add all numbers to hash table
2. for each no in array search for hash(9-a[i])

Combinations of two, or more?

#!/usr/bin/python

def main(self):
	a = range(10)
	b = []
	
	for i in range(9):
		b.append([a[i], a[9-i]])

	print '{0}'.format(b)

if __name__ == '__main__':
	main()

while( count!=7)
	{
	for(i=0;i<7;i++)
	{

		sum=A1[count];
		sum=sum+A1[i+1];

		if(sum==9)
		{
			cout<<"{"<<A1[count]<<","<<A1[i+1]<<"}"<<endl;
			
		}
}
	count++;
	}

#include<iostream>
#define MAX 7
int main(int argc,char **argv)
{
int arr[MAX]={0,4,2,3,5,6,9};
int com_num;
int end_index=MAX-1;
int index,sum=0;
std::cout<<"Enter commbination number"<<std::endl;
std::cin>>com_num;
for(index=0; index<MAX-1;)
{
sum=arr[index]+arr[end_index];
if(sum==com_num)
{
std::cout<<"{"<<arr[index]<<","<<arr[end_index]<<"}"<<"\t";
}
end_index--;
if(end_index==index)
{
index++;
end_index=MAX-1;
}
}
}complexity o(n)

def printCombination(numList, summ):
	numDict = {}
	for num in numList:
		partner = summ - num
		if partner in numDict:
			print "(%i, %i)" %(num, partner)
		else:
			numDict[num] = Truedef printCombination(numList, summ):
	numDict = {}
	for num in numList:
		partner = summ - num
		if partner in numDict:
			print "(%i, %i)" %(num, partner)
		else:
			numDict[num] = True

#include<stdio.h>
#include<conio.h>
main()
{
	int i,j,found;
	int a[]={0,1,2,3,5,6,7,8,9};
	for(i=0;i<8;i++)
	{
		found=0;
		for(j=i+1;j<9 && found==0;j++)
		{
			if(a[i]+a[j]==9)
			{
				printf("{%d,%d} ",a[i],a[j]);
				found=1;
			}
		}
	}
	getch();
}

public static void SumTwoElement(int[] array)
        {
            array = MergeSort(array);
            for (int i = 0, j=array.Length-1; i < array.Length&& j>0; i++,j--)
            {
                if (array[i] + array[j] == 9)
                {
                    Console.WriteLine("{0},{1}",array[i],array[j]);
                }
                
            }
        }