Amazon Interview Question Testing / Quality Assurances
Country: India
Interview Type: In-Person
Even with the optimization, the solution would be O(N^2), because you're summing up every pair of numbers.
Here I propose a solution, which would be linear time. It has two parts. I'm assuming the array is sorted in ascending order and has only +ve numbers (can be modified for -ve numbers also)
Part 1. Find the number(5) within array using binary search. O(Log N) run time
Part 2. Now, any elements after this number i.e. which are > 5 are useless, so we'll focus on the subarry to the left of 5(including 5) i.e. [0, 1, 2, 3, 5].
Lets say this subarray is A. Let N = 5
Have two pointers i and j. i = 0 and j = A.length
while(i<j){
if(A[i] + A[j] < N) {
/* if sum of elements at current indices is < required number,
we need to increase the sum, so i++
*/
i++;
}
else if (A[i] + A[j] > N){
//decrese the sum
j--;
}
else{
//we have a match,
print i and j and
decrease sum: j--;
}
}
i like the point of u bringing in about "ignoring numbers greater than 5" .That is a simple way of reducing the computation :)
BTW how is this complexity calcuated . What do u mean by the solution would be O(N^2) etc . I am new to this
Thanks!
Complexity would be too big a topic to explain here.
In a few lines, it means what would be worse case number of calculations required to achieve the result.
In your algorithm, you're comparing each number with every different one. So, if the array had N numbers, starting from the 1st, # comparisons:
N-1 + N-2(for the second #) + N-3 + .. + 1 = sum of first N-1 natural # = (N-1)(N-2)/2 = N^2 -3N + 2
The highest power in this case is N^2, so your operation could take that much time in worst case.
I recommend looking up big O notation on google/youtube. Also bigocheatsheet dot com has some good info..
Will your solution works for this input ??
I/p Sub Array = [0,1,2,3,4] , Sum = 6
Answer should contain 1+2+3 = 6
No I don't think it'll work in this case. I'm just looking for two elements that add up to the sum, not more than that.
If we want all such elements, then its a NP hard problem, we'll have to calculate all the subsets.
If we want sets of 3 nos, in your 'if', just before incrementing 'i', check if the number (5-(a[i] + a[j])) is present in the array. If it is then that number, a[i] and a[j] become your 3-tuple. Similarly in your else, check if a[j] can be made up by 2 other numbers present in the array. If yes, then a[i] and these 2 numbers become your 3-tuple.
nharryp, if multiple elements are required here, then why just 3 tuples? It could be 4 or N tuples, right?
I agree with puneet that it is NP hard problem where all the subsets needs to be evaluated.
For any combination of elements :
Presteps:
-sort the list
-keep only those elements which are < sumWeHaveToFind and pass to following function:
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.TreeSet;
public class Comb {
public HashSet getAllSum(ArrayList al, int val) {
int counter = 0;
int x = al.size();
long l = (long) Math.pow(2, x);
HashSet result = new HashSet();
while (counter < l) {
int temp = 0;
String str = Integer.toBinaryString(counter);
// System.out.println("---"+str) ;
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '1') {
temp = temp + (int) al.get(str.length() - 1 - j);
}
}
if (temp == val) {
StringBuffer res = new StringBuffer();
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '1') {
res.append(al.get(str.length() - 1 - j));
res.append('+');
// System.out.print(al.get(str.length()-1-j));
// System.out.print("+");
}
}
String resu = res.toString();
result.add(resu);
}
counter++;
}
return result;
}
public static void main(String[] args) {
Comb b = new Comb();
ArrayList al = new ArrayList();
al.add(1);
al.add(1);
al.add(1);
al.add(1);
al.add(1);
al.add(2);
al.add(2);
al.add(2);
al.add(3);
al.add(3);
al.add(3);
HashSet hst = b.getAllSum(al, 6);
Iterator itr = hst.iterator();
while (itr.hasNext()) {
String st = (String) itr.next();
System.out.println(st);
}
}
}
I think what we need here is all possible subsets which sum to a particular value say s.
In case of all positive values we can sort and ignore values >s and get subsets of remaining values which sum to s.
In case of both negative and positive values we need to go for subsets of whole array and sorting would be irrelevant in this case.
My solution is O(n), assuming, we need to give a pair of numbers whose sum matches the value asked for.
(1) create a hash map of <key=(the numbers given in list), value= the frequency of the number>
(2) start with first number in the list and subtract this number from the sum (if the number is positive), if its negative then add.
(3) search in hash map for the difference from step 2 if present then print the pair else proceed with step 2.
Note: few assumptions
(1) sum requested is positive, but the above algo can be modified to make it work for
negative sums.
(2) we want to print pair of numbers only.
I just wrote this function to perform the same during the interview.. It does do the job. I think there might be some optimization possibilities and some static checks can be changed. But its simple with recursion. It provides for all scenarios 14, 014, 023 etc/
public class FindSum {
int[] number;
int length;
int sum = 0;
StringBuilder s;
FindSum(int[] input) {
number = input;
length = number.length;
s = new StringBuilder();
}
public void caller() {
for (int j = 0; j < number.length; j++) {
find(j);
sum = 0;
s.setLength(0);
}
}
public void find(int i) {
sum = sum + number[i];
s.append(number[i]);
if (sum > 5) {
return;
}
if (sum == 5) {
// sum-=number[i];
System.out.println("Answer:" + s);
// s.setLength(s.length()-1);
return;
}
for (int j = i + 1; j < number.length; j++) {
// System.out.println(sum);
// System.out.println("Answer:"+s);
find(j);
sum -= number[j];
s.setLength(s.length() - 1);
}
return;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int search = 5;
int array[] = { 0, 1, 2, 3, 4, 6, 7, 8 };
int j = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] < search) {
array[j++] = array[i];
}
}
int[] b = new int[j];
System.arraycopy(array, 0, b, 0, j);
array = b;
FindSum test = new FindSum(array);
test.caller();
}
}
I faced similar question but this time there were both positive and negative values in the array. This is my code.... Pls tell me whether O(n^2) complexity can be improved.
class SumArray
{
public static void main(String args[])
{
int arr[] = {2,1,4,7,3,-3,-8,0,-1,-4,-7,6};
String s;
int n = arr.length;
for(int i=0;i<n-1;i++)
{
int item = arr[i];
int sum = item;
s = arr[i]+""+",";
two: for(int j=i+1;j<n;j++)
{
sum+= arr[j];
s = s+arr[j]+",";
if(sum!=0)
{
continue two;
}
else
{
System.out.println(s);
s=null;
}
}
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SumArray{
private static int[] origArray = {0,1,2,3,4,5,6,7,8,9};
private static int keyValue = 5;
public static void printPermutations(int[] n, int[] Nr, int idx) {
if (idx == n.length) {
int sum = 0;
List<Integer> list = new ArrayList<Integer>();
for(Object val: n) {
if(!list.contains(val)) {
list.add((Integer) val);
sum += (Integer) val;
}
}
if(sum==keyValue){
System.out.println("sum:"+Arrays.toString(list.toArray(new Object[0]))+"="+sum);
}
return;
}
for (int i = 0; i <= Nr[idx]; i++) {
n[idx] = i;
printPermutations(n, Nr, idx+1);
}
}
public static void main(String[] args){
int arrNewLength = 0;
Arrays.sort(origArray);
for(int i=0;i<origArray.length;i++){
if(origArray[i]<=keyValue){
arrNewLength++;
}else{
break;
}
}
int[] tmpArr = new int[arrNewLength];
System.arraycopy(origArray, 0, tmpArr, 0, arrNewLength);
System.out.println(Arrays.toString(origArray));
System.out.println(Arrays.toString(tmpArr));
int[] n = new int[arrNewLength];
printPermutations(n, tmpArr, 0);
}
}
Need some improvement, but works.
my @arr=(1,2,4,5,6,7,9,11,12,14,0,3);
my @array1=sort {$a <=> $b} @arr;
for (my $i=0; $i<=$#array1;$i++){
if ($array1[$i] > 5){
splice (@array1, $i , $#array1+1 - $i);
}
}
print "@array1 \n";
for (my $j=0; $j<=$#array1;$j++){
for (my $k=$#array1; $k>=$j;$k--){
if (($array1[$j] + $array1[$k]) == 5){
print "$array1[$j],$array1[$k] \n";
}
}
}
public class sumElement {
public static void main(String[] args) {
int array[] = {0,1,2,3,4,5,6};
int j = array.length-1;
for(int i = 0; i< j; ){
if(array[i]+array[j] < 5)
i++;
else if(array[i]+array[j] > 5)
j--;
else
{
System.out.println("Sum of "+ array[i] +" + "+array[j] +" = 5");
j--;
}
}
}
}
#include<stdio.h>
#include<stdlib.h>
int find(int a,int b, int arr[10])
{
int flag=0;
int i;
for(i=0;i<10;++i)
{
if(arr[i]==a || arr[i]==b )
flag++;
}
if(flag==2 || a==b)
return 1;
else
return 0;
}
void main()
{
int arr[10];
printf("Enter array ");
int i;
for(i=0;i<10;++i)
{
scanf("%d",&arr[i]);
}
for(i=0;i<10;++i)
{
printf("\n%d\n",arr[i]);
}
printf("Enter element ");
int el;
scanf("%d",&el);
for(i=0;i<el;++i)
{
if(find(i,el-i,arr))
printf("%d + %d = %d\n",i,el-i,el);
}
}
It is an O(n) solution. It assumes that array contains only positive numbers.
quite a simple solution here in c!
#include<stdio.h>
#include<conio.h>
void main()
{ int a[10];
int i,j,k;
for(i=0;i<10;i++)
scanf("%d ",&a[i]);
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if((a[i]+a[j])==5)
printf("\n %d %d",a[i],a[j]);
else
{
if((a[i]+a[j])<5)
for(k=j+1;k<10;k++)
if(a[i]+a[j]+a[k]==5)
printf("\n %d %d %d",a[i],a[j],a[k]);
}
}
#include <stdio.h>
#define MAX 10
int array[MAX] = {1,2,3,4,5, 6, 7, 8, 9, 10};
int temp[MAX] = {0};
void FindCombo(int number)
{
int i, j, k, t, sum = 0;
for(i = 0; i < MAX; i++)
{
memset(temp, 0 , MAX);
t = 0;
sum = array[i];
temp[t++] = array[i];
for(k = i + 1; ((k < MAX)&&(sum != number)); k++ )
{
memset(temp, 0 , MAX);
t = 0;
sum = array[i];
temp[t++] = array[i];
for(j = k; ((j < MAX)&&(sum < number)); j++)
{
sum = sum + array[j];
if(sum <= number)
{
temp[t++] = array[j];
}
}
}
if(sum == number)
{
int x;
printf("\nprinting set\n");
for(x = 0; x < t; x++)
{
printf("%u ", temp[x]);
}
printf("\n***********\n");
}
}
}
main()
{
FindCombo(10);
}
import java.util.*;
public class FirstDupicate {
public static void main(String []args)
{
Integer keyValue=1;
int[] num={0,1,2,3,4};
int sum=6;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<num.length;i++){
int temp=0+num[i];
for(int j=i+1;j<num.length;j++){
temp=temp+num[j];
map.put(keyValue,temp);
keyValue++;
}
}
Iterator<Integer> keySetIterator = map.keySet().iterator();
while(keySetIterator.hasNext()){
Integer key = keySetIterator.next();
if(map.get(key)==sum){
System.out.println("key="+key+"value "+map.get(key));
}
}
}
}
/* Below program will provide all the sets having sum equal to given number, not only the set of 2 numbers */
/* This program will provide all the list of numbers having sum equal to some particular number. This list could have 1,2,3,4
,5,.... numbers. for example, if in a list, there are 2,4,6,5,3,1 numbers, and we have to find the numbers having sum as 7, t
hen the sets of numbers would be {1,6},{2,5},{3,4},{1,2,4} */
#include<stdio.h>
struct list
{
int data;
struct list * next;
}
;
struct list * arr_list[200];
int list_count=0,prev=0,row=0,prev_row=0;
int fact(int i)
{
int x,y,z=1;
for(x=1;x<=i;x++)
{
z=z*x;
}
return(z);
}
void check_display()
{
/*int x,y;
struct list * temp;
printf("\n inside check_display \n");
for(x=0;x<list_count+1;x++)
{
temp=arr_list[x];
printf("%d. ",x);
while(temp!=NULL)
{
printf(" %d -> ",temp->data);
temp=temp->next;
}
printf("\n");
}*/
}
void sum_check(int num)
{
int x,y,sum=0;
struct list * temp;
printf("\n inside sum_check \n");
for(x=0;x<list_count;x++)
{
temp=arr_list[x];
//printf("<%.3d>. ",x);
sum=0;
while(temp!=NULL)
{
sum=sum+temp->data;
//printf(" %d -> ",temp->data);
temp=temp->next;
}
if(sum==num)
{
printf("\n for LIST <%d> , sum is <%d> \n",x,sum);
}
//printf("\n");
}
}
void display()
{
int x,y;
struct list * temp;
printf("\n inside display \n");
for(x=0;x<list_count;x++)
{
temp=arr_list[x];
printf("<%.3d>. ",x);
while(temp!=NULL)
{
printf(" %d -> ",temp->data);
temp=temp->next;
}
printf("\n");
}
}
void adr_cpy(struct list** target,struct list** source)
{
printf("\n inside adr_cpy \n");
struct list* temp;
temp=(struct list*)malloc(sizeof(struct list));
(*target)=temp;
while((*source)!=NULL)
{
temp->data=(*source)->data;
(*source)=(*source)->next;
temp->next=(struct list*)malloc(sizeof(struct list));
temp=temp->next;
}
temp=NULL;
}
calcsum(int j, int num, int count, int arra[])
{
int check_dup=0,x,y,z,r=0,local_list_count=0,temp_list_count=0;
struct list *temp,*temp2,*temp3,*temp4;
printf("\n Inside calcsum \n");
printf("Print the list of pairs containing <%d> elements from the array \n",j);
if(j<=1)
{
x=0;
for(x=0;x<count;x++)
{
//if(arra[x]==num)
//{
printf("\n list of numbers having only 1 set which satisfies the condition \n");
printf("arra[%d] is <%d> num <%d> \n",x,arra[x],num);
arr_list[list_count]=(struct list *) malloc(sizeof(struct list));
arr_list[list_count]->data=arra[x];
arr_list[list_count]->next=NULL;
list_count++;
//}
}
r=fact(count)/(fact(j)*fact(count-j));
row=r+row;
printf("\n row is <%d> for count <%d> j <%d> \n",row,count,j);
prev=1;
}
else if(j==2)
{
for(x=0;x<count-1;x++)
{
//if(arra[x] < num)
//{
for(y=x+1;y<count;y++)
{
//if(arra[y] < num)
//{
//if((arra[x] + arra[y])==num)
//{
arr_list[list_count]=(struct list *) malloc(sizeof(struct list));
temp=(struct list *) malloc(sizeof(struct list));
temp->data=arra[y];
temp->next=NULL;
arr_list[list_count]->data=arra[x];
arr_list[list_count]->next=temp;
list_count++;
//}
//}
}
//}
}
r=fact(count)/(fact(j)*fact(count-j));
row=r+row;
r=fact(count)/(fact(j-1)*fact(count-(j-1)));
prev_row=r+prev_row;
printf("\n row is <%d> for count <%d> j <%d> \n",row,count,j);
prev=2;
check_display();
}
else
{
r=fact(count)/(fact(prev)*fact(count-prev));
x=prev_row;
printf("\n calsum : else <%d> \n",j);
for(y=0;y<count;y++) /* check for arra[y] element and add it to the lists */
{
temp=arr_list[x];
for(x=prev_row;x<row;x++) /* check for the lists which are ;previously created for j-1 */
{
printf("\n check for x list <%d> \n",x);
temp=arr_list[x];
printf("\n in the below loop, check whether %d element exist in list %x \n",arra[y],x);
while(temp!=NULL)
{
printf("\n data is <%d> element is <%d> \n",temp->data,arra[y]);
if(arra[y]==(temp->data))
{
break;
}
temp=temp->next;
}
temp4=(struct list *) malloc(sizeof(struct list));
printf("\n Check whether temp is NULL, if NULL , add the element else check next list \n");
if(temp==NULL) /* create new list and insert arra[y] into it when arra[y] doesnt exist in that list */
{
fflush(stdout);
printf("\n in the list <%d> , element <%d> doesnt exist, so add \n",x,arra[y]);
printf("\n inside add if condition to add the element \n");
temp=arr_list[x];
if(arra[y] < temp->data) /* number to be inserted is the first element of new list */
{
printf("\n if element should be added at first position \n");
temp2=(struct list *) malloc(sizeof(struct list));
temp2->data=arra[y];
temp2->next=temp;
/* CROW arr_list[x]=temp2; */
arr_list[list_count]=(struct list *) malloc(sizeof(struct list));
arr_list[list_count]->data=temp2->data;
arr_list[list_count]->next=temp2->next;
list_count=list_count+1;
/* CROW added above */
//arr_list[list_count]=(struct list *) malloc(sizeof(struct list));
//arr_list[list_count]=temp2;
//list_count++;
}
else
{
printf("\n if element not to be added at first position \n");
arr_list[list_count]=(struct list *) malloc(sizeof(struct list)); /* CROW */
arr_list[list_count]=temp4;
while(temp->next!=NULL)
{
printf(" data <%d> next_data <%d> element <%d> \n",temp->data,(temp->next->data),arra[y]);
printf("\n insert <%d> into list <%d> \n",temp->data,list_count);
temp4->data=temp->data; /*CROW */
if((temp->data < arra[y]) && ((temp->next->data) > arra[y]))
{
printf("\n if element to be added in between the limits \n");
temp2=(struct list *) malloc(sizeof(struct list));
temp2->data=arra[y];
// CROW temp2->next=temp->next;
// CROW temp->next=temp2;
//temp2->next=temp->next;
// CROW temp->next=temp2;
break;
}
temp4->next=(struct list *) malloc(sizeof(struct list)); /* CROW */
temp4=temp4->next;
temp=temp->next;
}
if(temp->next==NULL)
{
//temp4->next=(struct list *) malloc(sizeof(struct list)); /* CROW */
//temp4=temp4->next;
printf("\n insert %d into list <%d>\n",temp->data,list_count);
temp4->data=temp->data;
printf("\n if element to be added in the end of the list \n");
temp2=(struct list *) malloc(sizeof(struct list));
temp4->next=(struct list *) malloc(sizeof(struct list));
temp4->next=temp2;
printf("\n insert %d into list <%d>\n",arra[y],list_count);
temp2->data=arra[y];
temp2->next=NULL;
// CROW2 temp->next=temp2;
//temp4->next=temp2;
list_count++;
}
else /* CROW */
{
check_display();
printf("\n inside else to populate remaining list \n");
//arr_list[list_count]->data=temp->data;
temp4->next=(struct list *) malloc(sizeof(struct list));
temp4=temp4->next;
temp4->data=temp2->data;
printf("\n insert <%d> into list <%d> \n",temp2->data,list_count);
temp=temp->next;
check_display();
while(temp!=NULL)
{
printf("\nwhile insert <%d> into list <%d> \n",temp->data,list_count);
temp4->next=(struct list *) malloc(sizeof(struct list));
temp4=temp4->next;
temp4->data=temp->data;
temp=temp->next;
}
temp4->next=NULL;
list_count++;
}
}
}
display();
printf("\n check for duplicacy \n\n");
for(check_dup=row;check_dup<list_count-1;check_dup++)
{
printf("\n check_dup is <%d> list_count is <%d> \n",check_dup,list_count);
temp=arr_list[check_dup];
temp2=arr_list[list_count-1];
fflush(stdout);
printf("\n before while \n");
while(((temp->data)==(temp2->data)) && temp->next!=NULL)
{
temp=temp->next;
temp2=temp2->next;
printf(" check data \n");
}
printf(" after while \n");
fflush(stdout);
if((temp->next==NULL && temp2->next==NULL) && (temp->data)==(temp2->data))
{
printf("\n duplicacy found \n");
list_count--;
//free(arr_list[list_count-1]);
break;
}
}
/* temp list created with arra[y] .. check if duplicate already created */
//arr_list[list_count]=(struct list *) malloc(sizeof(struct list));
//arr_list[list_count]->data=j;
//list_count++;
display();
}
}
r=fact(count)/(fact(j)*fact(count-j));
row=r+row;
r=fact(count)/(fact(j-1)*fact(count-(j-1)));
prev_row=r+prev_row;
printf("\n row is <%d> for count <%d> j <%d> \n",row,count,j);
prev++;
//calcsum(j-1,num,count,arra);
}
}
sum_series(int num, int count, int arra[])
{
int i,j,k;
printf("inside sum_series \n");
for(i=0;i<count;i++)
{
printf("\n element <%d> <%d> \n",i,arra[i]);
}
for(j=1;j<=count;j++)
{
//if(arra[j-1]<num )
calcsum(j,num,count,arra);
}
}
void main()
{
int i=0,j=0,k=0,temp;
int arra[10],arrb[10];
int num;
printf("\nEnter number of digits for the arra y : ");
scanf("%d",&k);
for(i=0;i<k;i++)
{
printf("\n Enter Element <%d> \n",i);
scanf("%d",&arra[i]);
}
printf("\n Enter number : ");
scanf("%d",&num);
printf("\n Sort the array \n");
for(i=0;i<k;i++)
{
for(j=i+1;j<k;j++)
{
if(arra[i]>arra[j])
{
temp=arra[i];
arra[i]=arra[j];
arra[j]=temp;
}
}
}
for(i=0;i<k;i++)
{
printf("\n element <%d> <%d> \n",i,arra[i]);
}
sum_series(num,k,arra);
display();
sum_check(num);
}
Is the array given sorted?? (example given in question I assume so)
If yes then the solution can be to read the array from start and end together, say with indexes s and e respectively. Sum the values at the indexes and see if the sum is greater than given value then decrements e and if smaller then increment s. If the sum is found then print the pair and together increment and decrements s and e respectively till s!=e. This also will handle negative numbers.
O(n) complexity...
public class sumArr {
public static void main(String[] args) {
int[] arr = {0,1,2,3,5,6,7,11,12,14,20};
int i, j,sum=5;
try{
for(i=0; i < arr.length; i++)
{
for(j=1; j < arr.length; j++)
{
if((arr[i]+arr[j]) == 5)
{
System.out.println("i->"+arr[i]+" j->"+arr[j]);
}
}
}
}catch(Exception e)
{
System.out.println("Array out of bounds");
}
}
Complete & the Simplest Perl Solution to find combination of elements which sum to 5.
#!/usr/bin/perl -w
@arr = qw(0 1 2 3 4 5 6 7 8 9 10);
for($i=0; $i<$#arr; $i++)
{
if((5 - $arr[$i]) >= 0)
{
push @reqArr, $arr[$i];
}
}
print "@reqArr\n";
for($j=0; $j<=$#reqArr; $j++)
{
for($k=0; $k<$#reqArr; $k++)
{
if(($reqArr[$j]+$reqArr[$k]) == 5)
{
print "$reqArr[$j], $reqArr[$k]\n";
}
if(($reqArr[$j]+$reqArr[$k]+$reqArr[$k+1]) == 5)
{
print "$reqArr[$j], $reqArr[$k], $reqArr[$k+1]\n";
}
}
}
Execution :--
[oracle@dev1 perl_scripts]$ ./prog_4.pl
0 1 2 3 4 5
0, 2, 3
1, 4
2, 1, 2
2, 3
3, 2
4, 0, 1
4, 1
5, 0
Thanks,
Puneet Agrawal
my $sum=9;
my @array=(-1,3,2,4,5,7,6,9,0,10);
my $var;
my %has;
my $temp;
foreach $var (@array){
if($var<$sum){
$temp=$sum-$var;
$has{$var}=1;
if($has{$temp}==1)
{
print "Two numbers whoes sum is $sum are $var,$temp \n";
}
}
else{
$temp=$sum-$var;
$has{$var}=1;
if($has{$temp}==1)
{
print "Two numbers whoes sum is $sum are $var,$temp \n";
}
}
}
Works fine for atleast 3 digits .
@arr = (0,1,2,3,4,5,6,7);
print "\nEnter number\n";
$n = <STDIN>;
for ($i = 0 ; $i < $#arr ; $i++) {
for ($j = $i+1; $j < $#arr ; $j++) {
if ($arr[$i] + $arr[$j] == $n) {
print "\n$arr[$i] and $arr[$j]\n";
}
if ($arr[$i] + $arr[$j] < $n ) {
for ($k = $j+1 ; $k < $#arr ; $k++) {
if ($arr[$i] + $arr[$j] +$arr[$k] == $n) {
print "\n$arr[$i] and $arr[$j] and $arr[$k]\n";
}
}
}
}
}
import java.util.ArrayList;
import java.util.List;
class SumToX{
static List<Integer> list = new ArrayList<>();
public static void printsums(int X, int[] arr){
sumToX(arr, X, 0, 0);
}
private static void sumToX(int[] arr, int X, int total, int index){
if(total > X) return;
if(total == X){
for(Integer y:list){
System.out.print(" " + y);
}
System.out.println("");
return;
}
for(int n = index; n <= X && n < arr.length; n++){
list.add(arr[n]);
sumToX(arr, X, total+arr[n], n+1);
list.remove((Integer)arr[n]);
}
}
}
//counting no. of element sum = 5
void swap(int A[], int tr, int sr)
{
int temp = A[tr];
A[tr] = A[sr];
A[sr] = temp;
}
int partition(int A[], int start, int end)
{
int pivot = A[end];
int partitionIndex = start;
for(int i = start; i < end; i++)
{
if(pivot >= A[i])
{
swap(A,i,partitionIndex);
partitionIndex++;
}
}
swap(A,end,partitionIndex);
return partitionIndex;
}
void QuickSort(int A[], int start, int end)
{
if(start < end)
{
int partitionIndex = partition(A,start,end);
QuickSort(A,start,partitionIndex - 1);
QuickSort(A,partitionIndex + 1, end);
}
}
int main()
{
int A[] = {0,1,2,4,3,6,7,5,11,13,20};
int count = 0;
QuickSort(A,0,10);
for(int i = 0; i < 10; i++)
cout << A[i] << ",";
cout << endl;
int result = 5;
int index = 0;
bool visited[10]={};
for(int i = 0; i < 10; i++)
{
visited[i] = false;
if(A[i] == result)
{
index = i;
break;
}
}
for(int i = 0; i <= index; i++)
{
for(int j =0; j<= index; j++)
{
if(A[i] + A[j] == result && (visited[i] == false && visited[j] == false))
{
visited[i] = visited[j] = true;
count++;
}
}
}
cout << "count value for sum "<< result << " is "<< count;
cout <<endl;
return 0;
}
import java.util.Arrays;
public class FindSubArray {
public static int[] arr = { -1, -5, 2, 3, 1, 2, 3, 4, 6, 7, 7, 4, 5, 6, 3, 6, 8, 9, 12, 15, 12, 14, 1 };
public static void main(String[] args) {
Arrays.sort(arr);
int target = 12;
findAllElementsSumingToTarget(arr, target);
}
public static void findAllElementsSumingToTarget(int[] arr, int target) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
int count = 1; // This variable takes care of summing sub arrays in while loop
while (count < arr.length) {
for (int j = i + 1; j < arr.length; j++) { //This J loop is to iterate through each element (i+1)
sum = arr[i] + sumSubArray(j, count); // sumSubArray will add elements starting from i+1 to arr.length
if (sum == target && arr[i] != target) {
matchedArray(i, j, count);
}
}
count++;
}
count = 1;
}
}
public static int sumSubArray(int start, int elements) {
int sum = 0;
for (int i = start; i <= elements; i++)
sum += arr[i];
return sum;
}
public static void matchedArray(int start, int subArrayStart,
int lengthOfSubArray) {
if (lengthOfSubArray > 1) {
System.out.print("\nFound Array : " + arr[start] + " ,");
for (int i = subArrayStart; i <= lengthOfSubArray; i++)
System.out.print(arr[i] + " ,");
System.out.println();
}
}
}
{
import java.util.Arrays;
public class FindSubArray {
public static int[] arr = { -1, -5, 2, 3, 1, 2, 3, 4, 6, 7, 7, 4, 5, 6, 3, 6, 8, 9, 12, 15, 12, 14, 1 };
public static void main(String[] args) {
Arrays.sort(arr);
int target = 12;
findAllElementsSumingToTarget(arr, target);
}
public static void findAllElementsSumingToTarget(int[] arr, int target) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
int count = 1; // This variable takes care of summing sub arrays in while loop
while (count < arr.length) {
for (int j = i + 1; j < arr.length; j++) { //This J loop is to iterate through each element (i+1)
sum = arr[i] + sumSubArray(j, count); // sumSubArray will add elements starting from i+1 to arr.length
if (sum == target && arr[i] != target) {
matchedArray(i, j, count);
}
}
count++;
}
count = 1;
}
}
public static int sumSubArray(int start, int elements) {
int sum = 0;
for (int i = start; i <= elements; i++)
sum += arr[i];
return sum;
}
public static void matchedArray(int start, int subArrayStart,
int lengthOfSubArray) {
if (lengthOfSubArray > 1) {
System.out.print("\nFound Array : " + arr[start] + " ,");
for (int i = subArrayStart; i <= lengthOfSubArray; i++)
System.out.print(arr[i] + " ,");
System.out.println();
}
}
}
}
import java.util.Arrays;
public class FindSubArray {
public static int[] arr = { -1, -5, 2, 3, 1, 2, 3, 4, 6, 7, 7, 4, 5, 6, 3, 6, 8, 9, 12, 15, 12, 14, 1 };
public static void main(String[] args) {
Arrays.sort(arr);
int target = 12;
findAllElementsSumingToTarget(arr, target);
}
public static void findAllElementsSumingToTarget(int[] arr, int target) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
int count = 1; // This variable takes care of summing sub arrays in while loop
while (count < arr.length) {
for (int j = i + 1; j < arr.length; j++) { //This J loop is to iterate through each element (i+1)
sum = arr[i] + sumSubArray(j, count); // sumSubArray will add elements starting from i+1 to arr.length
if (sum == target && arr[i] != target) {
matchedArray(i, j, count);
}
}
count++;
}
count = 1;
}
}
public static int sumSubArray(int start, int elements) {
int sum = 0;
for (int i = start; i <= elements; i++)
sum += arr[i];
return sum;
}
public static void matchedArray(int start, int subArrayStart,
int lengthOfSubArray) {
if (lengthOfSubArray > 1) {
System.out.print("\nFound Array : " + arr[start] + " ,");
for (int i = subArrayStart; i <= lengthOfSubArray; i++)
System.out.print(arr[i] + " ,");
System.out.println();
}
}
}
import java.util.Arrays;
public class FindSubArray {
public static int[] arr = { -1, -5, 2, 3, 1, 2, 3, 4, 6, 7, 7, 4, 5, 6, 3, 6, 8, 9, 12, 15, 12, 14, 1 };
public static void main(String[] args) {
Arrays.sort(arr);
int target = 12;
findAllElementsSumingToTarget(arr, target);
}
public static void findAllElementsSumingToTarget(int[] arr, int target) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
int count = 1; // This variable takes care of summing sub arrays in while loop
while (count < arr.length) {
for (int j = i + 1; j < arr.length; j++) { //This J loop is to iterate through each element (i+1)
sum = arr[i] + sumSubArray(j, count); // sumSubArray will add elements starting from i+1 to arr.length
if (sum == target && arr[i] != target) {
matchedArray(i, j, count);
}
}
count++;
}
count = 1;
}
}
public static int sumSubArray(int start, int elements) {
int sum = 0;
for (int i = start; i <= elements; i++)
sum += arr[i];
return sum;
}
public static void matchedArray(int start, int subArrayStart,
int lengthOfSubArray) {
if (lengthOfSubArray > 1) {
System.out.print("\nFound Array : " + arr[start] + " ,");
for (int i = subArrayStart; i <= lengthOfSubArray; i++)
System.out.print(arr[i] + " ,");
System.out.println();
}
}
}
import java.util.Arrays;
public class FindSubArray {
public static int[] arr = { -1, -5, 2, 3, 1, 2, 3, 4, 6, 7, 7, 4, 5, 6, 3, 6, 8, 9, 12, 15, 12, 14, 1 };
public static void main(String[] args) {
Arrays.sort(arr);
int target = 12;
findAllElementsSumingToTarget(arr, target);
}
public static void findAllElementsSumingToTarget(int[] arr, int target) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
int count = 1; // This variable takes care of summing sub arrays in while loop
while (count < arr.length) {
for (int j = i + 1; j < arr.length; j++) { //This J loop is to iterate through each element (i+1)
sum = arr[i] + sumSubArray(j, count); // sumSubArray will add elements starting from i+1 to arr.length
if (sum == target && arr[i] != target) {
matchedArray(i, j, count);
}
}
count++;
}
count = 1;
}
}
public static int sumSubArray(int start, int elements) {
int sum = 0;
for (int i = start; i <= elements; i++)
sum += arr[i];
return sum;
}
public static void matchedArray(int start, int subArrayStart,
int lengthOfSubArray) {
if (lengthOfSubArray > 1) {
System.out.print("\nFound Array : " + arr[start] + " ,");
for (int i = subArrayStart; i <= lengthOfSubArray; i++)
System.out.print(arr[i] + " ,");
System.out.println();
}
}
}
'''for two digit output'''
import json
x_inp=input("Enter the array:")
x=json.loads(x_inp)
y_inp=input("Enter the summed number to find combinations:")
y=int(y_inp)
def combinations(x,y):
out=[]
for i in x:
for j in x:
summed=i+j
if summed==y:
a=(i,j)
out.append(a)
return (print("All the combinations are ",out))
combinations(x,y)
===================
''' For three digits output'''
import json
x_inp=input("Enter the array:")
x=json.loads(x_inp)
y_inp=input("Enter the summed number to find combinations:")
y=int(y_inp)
def combinations(x,y):
out=[]
for i in x:
for j in x:
for k in x:
summed=i+j+k
if summed==y:
a=(i,j,k)
out.append(a)
return (print("All the combinations are ",out))
combinations(x,y)
Here is the solution in Python3:
Using Sort method and Filtering >5 items. Using 'break' to reduce iterations.
L=[0,1,1,2,3,5,6,7,3,4,11,12,14,20]
L.sort()
K=[x for x in L if x<6]
print("K is", K)
print("L is ", L)
sum=0
for i in K:
for j in K[::-1]:
if i+j ==5:
sum+=i
break
print(sum)
print ("sum =", sum)
public class sumArr {
public static void main(String[] args) {
int[] arr = {0,1,2,3,5,6,7,11,12,14,20};
int i, j,sum=5;
try{
for(i=0; i < arr.length; i++)
{
for(j=1; j < arr.length; j++)
{
if((arr[i]+arr[j]) == 5)
{
System.out.println("i->"+arr[i]+" j->"+arr[j]);
}
}
}
}catch(Exception e)
{
System.out.println("Array out of bounds");
}
}
}
I did give below code in perl which checks for sum of 7 in this case
@arr=(1,2,4,5,6,7,9,11,12,14,0,3); $len=@arr; foreach(@arr) { print "$_ \t"; } print "\n"; for($i=0;$i<$len;$i++) { for($j=0;$j<$len;$j++) { if($i!=$j) { if($i+$j==@ARGV[0]) { print "\@arr[$i] plus \@arr[$j] is equal to @ARGV[0] \n"; } } } }But he asked me to optimize it
- i_learn April 11, 2014as there were redundancy happenning.
I couldn't find the optimization there but when i came home a gave a try found that the following should have been used
use if($i<$j) instead of if($i!=$j) then it will print duplicate also say 7+0 =0 once and 0+7 is 0 which is not optimised.
If there is even more simpler code please share as mine doesn't implement checking for and comparing the sum of more than 2numbers like even 1+2 +4 =7