I am practicing on CodingBat and trying the below question:

We want to make a row of bricks that is goal inches long. We have a number of small bricks (1 inch each) and big bricks (5 inches each). Return True if it is possible to make the goal by choosing from the given bricks.

Test cases:

• make_bricks(3, 1, 8) → True
• make_bricks(3, 1, 9) → False
• make_bricks(3, 2, 10) → True
• make_bricks(7, 1, 13) → False
• make_bricks(1, 4, 12) → False

When I run on my code on code editor(VSCode), I pass every test cases but when I do submit on the CodingBat(https://codingbat.com/prob/p118406) I am getting and error as Time out. Please can anyone explain me why or is there any error in my code below:

def make_bricks(small, big, goal):
    myNum = 5
    result = 0
    i = 1
    for i in range(big 1):
        if (i * myNum) == goal:
            return True
        elif (i * myNum) > goal:
            result = ((i * myNum) - myNum)
        elif (i * myNum) < goal:
            result = (i * myNum)
    for i in range(small   1):
        if result   i == goal:
            return True
    return False

print(make_bricks(20, 0, 19))

CodePudding user response：

You can calculate this without loops. It's the loops that are taking too much time. Some simple arithmetic and a couple of quick early checks should solve this issue:

def make_bricks(small, big, goal):
    big_ = big * 5
    max_ = big_   small
    if goal > max_:
        return False  # impossible
    if goal == max_:
        return True  # simple case - just use all the bricks
    if big_ > goal:
        big_ = goal // 5 * 5
    return big_   small >= goal

CodePudding user response：

The time out happens in this test case:

make_bricks(2, 1000000, 100003) 

That's probably because it's taking to much time to process the test case. In the test case above, the code is iterating over one million times, and in each iteration it's multiplying numbers and storing the result into result for no use in the first 999.999 loops:

        elif (i * myNum) < goal:
            result = (i * myNum)

You can do the calculations whithout a loop:

def make_bricks(small_bricks_available, big_bricks_available, goal):
    big_brick_size = 5
    small_brick_size = 1
    
    if goal < big_brick_size:
        return small_bricks_available >= goal
    
    big_bricks_needed = goal // big_brick_size
    
    if big_bricks_needed > big_bricks_available:
        big_bricks_needed = big_bricks_available

    goal -= big_bricks_needed * big_brick_size

    small_bricks_needed = goal // small_brick_size
    
    # the first comparison is not necessary, but I left it for clarity
    return big_bricks_available >= big_bricks_needed and small_bricks_available >= small_bricks_needed