CareerCup

I think it is better to start with the least number with fewest gaps. for example, 2 5_ _ and 2 10 _ _, start from 2 5 as 5 has only two combinations(e.g. 1, 4 and 2,3) wihle 10 has 5 combinations. For 3 47 _ _ _. it can be consider as one number and two gaps (e.g. 1 and gaps (2 46 _ _)). Any better ideas

I could not understand the problem, can anyone explain?

I think this is NP-Complete problem.

It's the same as subset sum problem: given a set of integers and an integer s, does any non-empty subset sum to s?

What do u think guys!!!!!

question doesn't make any sense to me

question doesn't make any sense to me

2;19: 1,18
3;47:2,45
2,20:3,17

gap[i] //contains numbers of empty nodes for sum[i]
sum[i] // assume sum[i] is in increasing order
//assume positive number,
totalGap = sum of gap[i] {i=0,...n-1}
maxSum = maximum of sum[i]
find totalGap of different numbers between 1 and maxSum.
with the limitation that : gap[i] numbers with get sum[i]
we has a flag array hashTab[1..maxSum] to indicate whether the number is taken.

Assuming the input "2 19 _ _ 3 47 _ _ _ 2 20 _ _" is an array of following 3 objects:
count sum
2 19 //object 1
3 47 //object 2
2 20 //object 3

Optional Step: Sort this array with key = sum in increasing order.

Use a backtracking(DFS) algorithm in which each iteration of the function fills next empty object. Fill the object with 'count' values not used before. If no such value exists return from present call.

Base case would be when all the objects are filled.

Pseudo Code:

//Prints all the possible solutions using backtracking (recursive algorithm)
perform(Pair arr[], int  size, int cur_index/*current index to fill, initially sent zero*/ ){
    if(cur_index == size){//zero-based
        printPairArray(arr);
        return;
    }
    int ways = number of combinations to cut arr[cur_index].sum into arr[cur_index].count parts
    for(int i=0; i< ways; i++){
        if any number in ith combination present in hash
            continue;
        arr.push(ith combination);
        hash.add(numbers in ith combination);
        perform(arr, size, cur_index+1);
    }
}

Thanks Mani. I just wrote a working code something similar to your algo.

import java.util.*;


class Calculate{

    public static Boolean check_if_keys_are_used(ArrayList keys,ArrayList alreadyUsed)
    {
   	int i,j;

	for(i=0;i<keys.size();i++)
	{
		for(j=0;j<alreadyUsed.size();j++)
		{
			if(keys.get(i) == alreadyUsed.get(j))
			{
				return true;
			}
		}	
	}
	
	return false;
		
    }


    public static void main(String[] args) 
    {
        int[][] Arr = new int[][]{{2,19},{3,47},{2,20},{6,82}};
        int num_of_entries = Arr.length;
 	int i,j,k,flag;
	int count,sum,temp_sum,temp;
 	ArrayList<Integer> alreadyUsed = new ArrayList();

	for (i = 0;i<num_of_entries ;i++) 
	{
		count = Arr[i][0];
		sum = Arr[i][1];
		temp_sum = sum;
		flag = 1;
		ArrayList<Integer> keys = new ArrayList(); 
		
		for (j=0;j<(count-1);j++) 
		{
			keys.add(flag++);
			temp_sum--;
		}
		
       
		while( temp_sum != 1) 
		{

			if(check_if_keys_are_used(keys,alreadyUsed))
			{
				for (k=0;k<(count-1);k++)	
				{
					temp = keys.get(k);
					temp++;
					keys.set(k,temp);
					temp_sum--;
				}
				
			}
			else
			{
				System.out.println("input : count- " + count + " sum - " + sum);
                                System.out.print("output : "); 
								
				for(k=0;k<keys.size();k++)
				{
					System.out.print(keys.get(k) + " "); 
					alreadyUsed.add(keys.get(k));
				}
				System.out.println(temp_sum); 
				
				break;

			}
			
		}
	}
    }
}