Java Solution HackerEarth Problem

 

Hackerearth link

Problem

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 less than or equals $100$ 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.

Constraints

• $1\le N,M\le 100$
• $1\le a_i,c_i\le 100$

 

Sample Input

2
1 2
3
3 4 5

Sample Output

2 3

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

If $e$ is an element of set $B$, then $e+2$ is an element of set $C$, so we must have $e\le 3$. Clearly, $e$ cannot be $1$ because $1+1=2$ is not an element of set $C$. Therefore, $B=\{2,3\}$.

Solution

/* IMPORTANT: Multiple classes and nested static classes are supported */

// uncomment this if you want to read input.

//imports for cufferedReader

//import java.io.cufferedReader;

//import java.io.InputStreamReader;

//import for Scanner and other utility classes

import java.util.*;

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail

class TestClass {

public static boolean f(int []arr,int num){

for (int i: arr){

if(i==num) return true;

}

return false;

}

public static void main(String args[] ) throws Exception {

/* Sample code to perform I/O:

* Use either of these methods for input

//cufferedReader

cufferedReader cr = new cufferedReader(new InputStreamReader(System.in));

String name = cr.readLine(); // Reading input from STDIN

System.out.println("Hi, " + name + "."); // Writing output to STDOUT

//Scanner

Scanner s = new Scanner(System.in);

String name = s.nextLine(); // Reading input from STDIN

System.out.println("Hi, " + name + "."); // Writing output to STDOUT

*/

// Write your code here

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int diff,f=0;

int a[]=new int[n];

for(int i=0;i<n;i++){

a[i]=sc.nextInt();

}

int m=sc.nextInt();

int c[]=new int[m];

for(int i=0;i<m;i++){

c[i]=sc.nextInt();

}

List <Integer> b=new ArrayList<Integer>();

for (int i: a){

for (int j: c){

if (i>j){

diff=i-j;

}else{

diff=j-i;

}

for(int k=0;k<b.size();k++){

Integer x=b.get(k);

int y=x.intValue();

if (y==diff){

f=1;

break;

}

}

if (f==0){

b.add(diff);

}

f=0;

}

}

f=0;

List<Integer> res=new ArrayList<Integer>(b);

for(int j=0;j<b.size();j++){

Integer x=b.get(j);

int y=x.intValue();

for (int i=0;i<n; i++){

if(f(c,a[i]+y)){

continue;

}else{

res.remove(x);

}

}

}

Collections.sort(res);

for(int j=0;j<res.size();j++){

System.out.print(res.get(j)+" ");

}

}

}