Discussion on Lisa's Workbook Challenge

2 months ago+ 0 comments

Instead of iterating over each problem, we can check if current_page falls within the range of problem_number to last_problem_on_page.

This approach reduces the time complexity for each page from O(k) to O(1) , where k is the maximum number of problems per page. Because it performs a single comparison per page rather than multiple comparisons for each problem on the page.

def work_book(n, k, arr):
    special_problems = 0
    current_page = 1

    for chapter in range(n):
        total_problems = arr[chapter]
        problem_number = 1

        while problem_number <= total_problems:
            # Calculate the last problem on the current page
            last_problem_on_page = min(problem_number + k - 1, total_problems)

            # Check if the current page contains a special problem
            if problem_number <= current_page <= last_problem_on_page:
                special_problems += 1

            # Move to the next page and update the problem number
            current_page += 1
            problem_number = last_problem_on_page + 1

    return special_problems

Cookie support is required to access HackerRank