A company is repainting its office – HackerRank Solution

   August 23, 2022

Problem

You can find the problem statement here.

Explanation

Subarrays with a sum less than or equal to 7 are

Length 1 – [2], [3], [5], [1], [1], [2], [1 ]
Length 2 – [2, 3], [5, 1], [1, 1], [1, 2], [2, 1]
Length 3 – [5, 1, 1], [1, 1, 2], [1,2,1]
Length 4 – [1, 1, 2, 1]

[1, 1, 2, 1] is the largest subarray with a sum less than or equal to 7 and has a length of 4.

Approach

The colors are arranged in a specific order so that each color complements the surrounding colors. Thus, we need to take consecutive elements only.

Our task can be simplified as finding the largest subarray of consecutive elements with a cost less than or equal to the budget.

We will be using the sliding window technique for solving this problem. We will start with the first element and continue adding the next elements until the cost is less than or equal to the budget. If the cost exceeds the budget, we shift the entire window to the right. Using this technique, we can calculate the cost for every consecutive subarray and get the maximum length.

Algorithm

left = 0
right = 0
max_len = 0
cost = 0

while left < n 
    right = left
    cost = 0
    curr_len = 0
    while right < n
        cost += prices[right]
        if cost <= money
            curr_len += 1
        right += 1

    if curr_len > max_len
        max_len = curr_len

    left += 1

return max_len

Code

def max_paints(prices, money):
    left = 0
    right = 0
    max_len = 0
    cost = 0

    while left < len(prices):
        right = left
        cost = 0
        curr_len = 0
        while right < len(prices):
            cost += prices[right]
            if cost <= money:
                curr_len += 1
            right += 1

        max_len = max(max_len, curr_len)
        left += 1

    return max_len


prices = [2, 3, 5, 1, 1, 2, 1]
money = 7

print(max_paints(prices, money))

Output

4

Optimizing code

Instead of checking for all subarrays, we can stop checking for subarray whose length can never be greater than the current max length that we have. We now end the loop where the left pointer can not have a greater length than the current max length.

def max_paints(prices, money):
    left = 0
    right = 0
    max_len = 0
    cost = 0
    n = len(prices)
    while n - left >= max_len:
        right = left
        cost = 0
        curr_len = 0
        while right < n:
            cost += prices[right]
            if cost <= money:
                curr_len += 1
            right += 1

        max_len = max(max_len, curr_len)
        left += 1

    return max_len


prices = [2, 3, 5, 1, 1, 2, 1]
money = 7

print(max_paints(prices, money))

Output

4

Best 100+ Python Projects with source code

Also Read:

Please review

★★★★★
Share:

Author: Ayush Purawr