CareerCup

Here is my method.
{{
import java.util.*;
public class Generate {
//start and end are inclusive
private static Set<Integer> eval(int[] values, int start, int end) {

if(start == end) {
return Collections.singleton(values[start]);
}

Set<Integer> results = new HashSet<Integer>();
//now break the array
// first array is from [start to i] and second array if from (i, end]
for (int i = start; i < end; i++) {
Set<Integer> lefts = eval(values, start, i);
Set<Integer> rights = eval(values, i + 1, end);


for(int left : lefts) {
for(int right: rights) {
results.add(left + right);
results.add(left - right);

results.add(left * right);
if(right != 0) {
results.add(left / right);
}

}

}
}

return results;
}

public static void main(String[] args) {
Set<Integer> a = eval(new int[]{6,6, 4, 4}, 0, 3);
int i=1;
while (a.contains(i)) {
i++;
}
System.out.println("number is:" + i);
}
}
}}

suppose ther is an empty list.

void find(int A[ ], int size , int index, int sum)
{
if(index >size)
{
list.add(sum);
return;
}
else
{
for(int i =0; i<4; i++)
{
if(i==0)
{
sum = sum + A[index];
find(A, size, ++index, sum);
}
if(i==1)
{
sum = sum - A[index];
find(A, size, ++index, sum);
}
if(i==2)
{
sum = sum * A[index];
find(A, size, ++index, sum);
}
if(i==3)
{
sum = sum / A[index];
find(A, size, ++index, sum);
}
}
}
}

List contain all the number that can be generated by given numbers
so find the smallest no. not present in list in O(nlogn) time using sorting.

note brackets can be there means all possible combination means brackets are making it easy.
the program will take O(4^n).

package amazon;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;


public class Get_All_Possible_Results {


public static ArrayList<Integer> compute(int[] test,int begin,int end, ArrayList<Integer> deal){
if(begin==end){
deal.add(test[begin]);
return deal;
}
HashMap<Integer,Boolean> keep=new HashMap<Integer,Boolean>();
if(begin==end-1){
deal.add(test[begin]+test[end]);
keep.put(test[begin]+test[end], true);

if(!keep.containsKey(test[begin]-test[end])){
deal.add(test[begin]-test[end]);
keep.put(test[begin]-test[end], true);
}

if(!keep.containsKey(test[begin]*test[end])){
deal.add(test[begin]*test[end]);
keep.put(test[begin]*test[end], true);
}

if(test[end]!=0){

if(!keep.containsKey(test[begin]/test[end])){
deal.add(test[begin]/test[end]);
keep.put(test[begin]/test[end], true);
}
}
return deal;
}


for(int let=begin;let!=end;let++){
ArrayList<Integer> left=compute(test,begin,let,new ArrayList<Integer>());
ArrayList<Integer> right=compute(test,let+1,end,new ArrayList<Integer>());
for(int i=0;i!=left.size();i++){
for(int j=0;j!=right.size();j++){
if(!keep.containsKey(left.get(i)+right.get(j))){
deal.add(left.get(i)+right.get(j));
keep.put(left.get(i)+right.get(j), true);
}

if(!keep.containsKey(left.get(i)-right.get(j))){
deal.add(left.get(i)-right.get(j));
keep.put(left.get(i)-right.get(j), true);
}
if(!keep.containsKey(left.get(i)*right.get(j))){
deal.add(left.get(i)*right.get(j));
keep.put(left.get(i)*right.get(j), true);
}
if(right.get(j)!=0){
if(!keep.containsKey(left.get(i)/right.get(j))){
deal.add(left.get(i)/right.get(j));
keep.put(left.get(i)/right.get(j), true);
}
}
}
}
}


return deal;
}
public static void main(String[] args) {
int [] test=new int[]{6,6,4,4};
ArrayList<Integer> results=compute(test,0,test.length-1,new ArrayList<Integer>());
Collections.sort(results);
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i));
}

}

}

u just sortt the array and use the operator in precedence order.