Medium Sum Set Problem | Hackerearth

Medium Sum Set Problem | Hackerearth

Question

Write a Program to find Medium Sum Set. In this problem, we define “set” is a collection of distinct numbers. For two sets A and B, we define their sum set is a set S(A,B)={a+b|a∈A,b∈B}. In other word, set S(A,B) contains all elements which can be represented as sum of an element in A and an element in B. Given two sets A,C, your task is to find set B of positive integers with maximum size such that S(A,B)=C. It is guaranteed that there is unique such set.

Input Format

The first line contains N denoting the number of elements in set A, the following line contains N space-separated integers ai denoting the elements of set A.

The third line contains M denoting the number of elements in set C, the following line contains M space-separated integers ci denoting the elements of set C.

Output Format

Print all elements of B in increasing order in a single line, separated by space.

 

Logic

  • Get Set A and Set C from the user.
  • Create a loop from 1 to 100 and check each integer when added with elements of  Set A produces only the items of elements of Set C.
  • For example Sample_2 : k = 4 produces -> k+1 = 5  and k+2 = 6. In this both 5, 6 are elements of Set C.
  • So add k = 4 to Set B.
  • Repeat the process until finding all possible items.

Program

[code lang=”java”]
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

class Hacker
{
public static void main(String arp[])
{
Scanner s = new Scanner(System.in);
int n = s.nextInt(); //Size of Set A
int t,m,temp;
boolean flag = true;

/* sA – set A
* sB – set B
* sC – set C */
Set<Integer> sA,sB,sC;
s1 = new HashSet<Integer>();
s2 = new HashSet<Integer>();
s3 = new HashSet<Integer>();

/*Getting Set A from user*/
for(int i =0; i<n ; i++)
{
t=s.nextInt();
sA.add(t);
}

m = s.nextInt(); //Size of Set C

/*Getting Set C from user*/
for(int j =0 ; j<m;j++)
{
t =s.nextInt();
sC.add(t);

}
for(int k =1; k<100;k++)
{

/*Use Iterator and loop through all elements of Set A*/
for (Iterator<Integer> it = sA.iterator(); it.hasNext();)
{
t = it.next();
temp = k+t; //Adding k with t(element of Set A)

if(sC.contains(temp)) //If ‘temp’ present in Set C
{
flag = true; //assign true if ‘k’ can produce element of Set C
}
else
{ flag =false;
break;
}
}
/*if ‘k’ can produce all the elements of Set C*/
if(flag)
sB.add(k); //Add k to Set B
}

/*print all items of set B*/
for(Iterator<Integer> it = sB.iterator();it.hasNext();)
{
System.out.print(it.next()+" ");
}
}
}
[/code]

You might also like…

Convert the String so it holds only distinct characters

 

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *