Google kickstart 2020 round A wrong answer

link to problem : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56

Problem There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend. What is the maximum number of houses you can buy?

Input The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a single line containing the two integers N and B. The second line contains N integers. The i-th integer is Ai, the cost of the i-th house.

Output For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of houses you can buy.

**Limits**
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ B ≤ 105.
1 ≤ Ai ≤ 1000, for all i.

**Test set 1**
1 ≤ N ≤ 100.

**Test set 2**
1 ≤ N ≤ 105.

**Sample Input** 
3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999

**Sample Output**  
Case #1: 2
Case #2: 3
Case #3: 0

In Sample Case #1, you have a budget of 100 dollars. You can buy the 1st and 3rd houses for 20 + 40 = 60 dollars. In Sample Case #2, you have a budget of 50 dollars. You can buy the 1st, 3rd and 4th houses for 30 + 10 + 10 = 50 dollars. In Sample Case #3, you have a budget of 300 dollars. You cannot buy any houses (so the answer is 0).

Here is my solution(Python 3):

T = int(input())

res = []
for i in range(T):
    N, B = map(int, input().split(' '))
    ai = list(map(int, input().split(' ')))
    ai.sort()
    for k in range(len(ai)):
        B = B - ai[k]
        if B < 0:
            res.append(k)
            break
        elif k == len(ai)-1:
            res.append(k+1)

for i in range(T):
    print("Case #", i+1, ":", res[i])

I have tried all the test cases I can think of and I’m getting the expected output. But when I try to submit, it says Sample Failed: wrong answer. Please let me know what exactly is wrong with my solution and how it can be improved.

Answer

I would suggest to simplify your code just a little and to be sure use string formatting. If it is python 3.6 and up you can use f-string or use string.format

# your second for loop
counter = 0
for k in ai:
    if B - k >= 0:
        B -= k
        counter += 1
    else:
        res.append(counter)
        break

for i in range(len(res)):
    # using f-string
    print(f"Case #{i+1}: {res[i]}")
    # using string format
    print("Case #{}: {}".format(i+1, res[i]))

Advertisement

Answer