JOIN
Get Time

   Problem Statement  

 Problem Statement for PayBill

Problem Statement

    

You have just finished your delicious Chinese food dinner with your friends, and divided up the bill. You are given the int[] meals, where each element of meals is the total amount owed by a given person. The number of elements in meals is the same as the number of people who ordered dinner. You also notice that there is totalMoney that has been placed on the table.

You now need to determine, based upon the price of each person's meal, and the amount of money that has been paid, which of your friends has paid. You are to return a int[] indicating who has already paid, where the value of each element is the zero-based index of a given person. The return int[] should be sorted in ascending order. The given data will be such that exactly one unique solution is possible.

 

Definition

    
Class:PayBill
Method:whoPaid
Parameters:int[], int
Returns:int[]
Method signature:int[] whoPaid(int[] meals, int totalMoney)
(be sure your method is public)
    
 

Constraints

-meals will contain between 1 and 50 elements, inclusive.
-Each element of meals will be between 1 and 10000, inclusive.
-totalMoney will be between 0 and 500000, inclusive.
-There will be exactly one unique solution to the problem.
 

Examples

0)
    
{ 1000, 1200, 1300 }
2500
Returns: { 1,  2 }
Clearly, the only way there can be 2500 on the table is if person 1 and 2 have paid, but person 0 has not.
1)
    
{ 100, 200, 350 }
300
Returns: { 0,  1 }
Of course, 100 + 200 = 300.
2)
    
{ 150, 200, 350, 400 }
900
Returns: { 0,  2,  3 }
Here, we have 150 + 350 + 400 = 900.
3)
    
{6584,6733,6018,5840,2723,4902,4260,
 5375,6745,1234,3000,8222,2472,
 4348,1716,9995,415,1234,2345,5679}
70630
Returns: { 0,  1,  3,  4,  5,  6,  8,  9,  11,  13,  14,  15,  16,  17,  19 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 219 Round 1 - Division II, Level Three