CareerCup

If (x:y) represent ratio (water:sugar) in a cup, then we need to find a subset out of 'n' cups where [Sum of x's] = [Sum of y's].

O(2^n) solution is trivial since there are 2^n subsets. How to optimize this?

Let us create a difference array, an array where each element is the difference (Y-X). Note that the difference should not be an absolute value.
Once the difference array is formed, we can apply the logic of subset of integers in an array summing to 0.

example:
X | 1 | 2 | 4 | 3 | 1 | 1 |

Y | 2 | 3 | 3 | 7 | 1 | 2 |

D | 1 | 1 | -1 | 4 | 0 | 1 | ---- Di=(Yi - Xi)

Now, on D, all we need to do is find a subset of integers which sums upto 0 (Dynamic programming can be used). The corresponding pairs of X and Y will be our answer.
Example, here we have 6 <x,y> pairs. Lets call them p1...p6.
Based on the values of D, possible solutions are as follows:
a) p5
b) p1, p3
c) p2, p3
d) p6, p3

struct _ratio {
    double sug;
    double wtr;
};

void conv_ratio_to_vol(struct _ratio* r, int n) //convert to volume in unit of cups
{
    int i;
    double denom;
    denom = r->sug + r->wtr;

    for (i = 0; i < n; i++) {
        r[i].sug /= denom;
        r[i].wtr /= denom;
    }
}

bool find_comb(struct _ratio* v, int n, double sum_sug, double sum_wtr)
{
    int i;
    int ret = false;

    if (n = 0) {
        return false;
    }
    // Two Choices for current cup 1. Not Sum it, 2 Sum it
    // 1 Dont Sum it
    for (i = n; i > 0; i--) {
        ret = find_comb(v + 1, n - 1, sum_sug, sum_wtr);
        if (ret) return ret;
    }

    // 2 Sum it
    sum_wtr += v->wtr;
    sum_sug += v->sug;
    if (sum_wtr == sum_sug) {
        return true;
    }
    for (i = n; i > 0; i--) {
        ret = find_comb(v + 1, n - 1, sum_sug, sum_wtr);
        if (ret) return ret;
    }
    return ret;
}

bool can_find_one_to_one(struct _ratio* r, int n)
{
    conv_ratio_to_vol(r, n);
    return find_comb(r, n, 0, 0); // O(2^n), can optimize this with DP?
}

How is it done in O(n) ?

in this we just have to tell if it's possible to get the ration 1:1,that just require the linear search and check for the ratio >=1 and the out of remaining one has to be <1

in this we just have to tell if it's possible to get the ration 1:1,that just require the linear search and check for the ratio >=1 and the out of remaining one has to be <1

We need to find cups so that the sum of rato should be equal to number of cups. But this will take so much complexity..

For example if we take two random cups with ratio 1/2 and 3/2 then sum is two and we took 2 cups so we found the result..Finding such cups will take finding all combinations of 1 cups to 50 cups which will result in exponential complexity..Please correct if i m wrong..

It is simple math problem.
Just check whether there exists some ratio <1 and some ratio > 1.
If yes, then possible , else not.
Say, there exists 2 cups one with ratio 1:6, and one with ration 2:1,
then as 1/6<1<2, so it is possible to create the final part by mixing different percentage from these 2 mixtures.

In this case, if we fill 7/22 part of the glass with sugar mixture of 1:6 and 15/22 part by 2:1 mixture, we will get the resultant mixture of water:sugar ratio of 1:1 .

I think this is a variant of the knapsack algorithm without repetition. Assume you have an array of doubles that have the ratios, and then you iterate through the array, and for each index you try every possible combination of ratios that can be formed with that index's ratio and all the indices ahead of it in the array. So for each index you iterate from index to end of array and add up weights seen of each current index to list of already seen weights of which you keep track of. If you find something equal to 1 you return true. If you find something greater than 1 you remove from list as that combo can't form anything less than 1. If you find something less than 1 you append to list as it might contribute to 1 with the adding of a weight in the future. So for each index i, you iterate from j=i to 50, and for each j you update the list of weights k which are just the ratios of sugar in the combo already seen. Runtime is still 0(2^n) because you still have to go through all possible combinations of the indices in the cups array.
Here's the code in java. If you see any bugs please comment below.

public boolean findMix(double [] cups)
	{
		for(int i=0; i< cups.length; i++)
		{
			ArrayList<Double> totals = new ArrayList<Double>();
			if(cups[i] == 1)
				return true;
			if(cups[i] < 1)
			{
				totals.add(cups[i]);
				if(findMixHelper(cups,totals,i))
					return true;
				else
					continue;
			}
		}
		return false;
	}
	boolean findMixHelper(double[] cups, ArrayList<Double> totals, int index)
	{
		if(index >= cups.length)
			return false;
		Object[] totalsArray = totals.toArray();
		for(Object o: totalsArray)
		{
			double t = (double) o;
			double curr = t + cups[index];
			if(curr == 1)
				return true;
			else if(curr < 1)
				totals.add(curr);
			//if curr > 1 it doesn't get added to totals, No Point!
		}
		return findMixHelper(cups,totals,++index);
	}

I think we can solve this problem using knapsack.
1. We do a linear run and find the total amount of water in the cups. Let this be C - capcity in knapsack
2. Then we sort the cups in terms of decreasing Sugar:Water ratio.
3. Then we feed the above values to 0-1 Knapsack problem.
4. In that we decrease the amount of water by C-c_cup_i and increase sugar by S+s_cup_i
5. If we get the 2 values equal we return the result.

Can't it be converted to subset sum problem then complexity would be O(total_sum*no_of_elements) rather than checking 2^n possibilities.