## Amazon Interview Question for Testing / Quality Assurances

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 2 vote

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
as 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

Comment hidden because of low score. Click to expand.
0

Did you ask if there would be negatives? If there wouldn't be any then you can ignore every number higher than sum

Comment hidden because of low score. Click to expand.
0
of 4 vote

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

Comment hidden because of low score. Click to expand.
2

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--;
}
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
3

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..

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

ans must include 0+2+3, 5 alone which is not included in ur answer.
using sum of subset will give answer in O(sum)^2 as we optimised problem

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
counter++;

}
return result;
}

public static void main(String[] args) {
Comb b = new Comb();

ArrayList al = new ArrayList();

HashSet hst = b.getAllSum(al, 6);
Iterator itr = hst.iterator();
while (itr.hasNext()) {
String st = (String) itr.next();
System.out.println(st);

}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
// s.setLength(s.length()-1);
return;
}

for (int j = i + 1; j < number.length; j++) {

// System.out.println(sum);
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();

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)) {
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

NP-hard -- subset-sum.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear if looking for sum of 2 entries exactly. O(k) if the input array is sorted & range is all positive integers. k here is the given value to be added up to.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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";
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import itertools
n = 5
num = [0,1,2,3,5,6,7,11,12,14,20]
l = []
l2 = []
for i in num:
if i <= n:
l.append(i)

for i in range(1, len(l)+1):
els = [list(x) for x in itertools.combinations(l, i)]
print els
for j in els:
if(sum(j)) == n:
l2.append(j)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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--;
}
}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks Larry@Perl

@arr=(1,2,4,5,6,7,9,11,12,14,0,3);
\$len=@arr;
print \$len;

foreach(@arr)
{
print "\$_ \t";
}
print "\n";

for(\$i=0;\$i<\$len;\$i++)
{
for(\$j=\$i;\$j<\$len;\$j++)
{
if(\$i+\$j == 5)
{
print "\$i+\$j makes 5\n\n";
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}
}

}
}``````

Comment hidden because of low score. Click to expand.
0

can u explain the logic u have used here?

Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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)
{
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]);
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;

//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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

What position is this question for? Is it for internship?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

array is in sorted order... we can break the array using binary search from x, then can find combinations from the numbers <x

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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";
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main()
{
int a[]={0,1,2,3,5,6,11,12,14,20};
int i,j,n=5;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
if(a[i]+a[j]==n)
{
cout<<a[i]<<"+"<<a[j]<<"="<<n<<endl;
}
}
}
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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";
}
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++){
sumToX(arr, X, total+arr[n], n+1);
list.remove((Integer)arr[n]);
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();

}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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();

}

}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();

}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();

}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

'''for two digit output'''

``````import json
x_inp=input("Enter the array:")
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:")
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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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");
}
}``````

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.