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 \in A, b \in 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 $a_{i}$ 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 $c_{i}$ 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()+" ");
        }
    }     
}

Medium Sum Set Problem | Hackerearth

Question

Logic

Program

You might also like…

Convert the String so it holds only distinct characters

Follow For Instant Updates

Sree Hari Sanjeev