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