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
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()+" "); } } }
You might also like…
Convert the String so it holds only distinct characters