HackerRank 'Lisas Workbook' Solution

Martin Kysel · June 22, 2016

Short Problem Definition:

Lisa just got a new math workbook. A workbook contains exercise problems, grouped into chapters.

  • …..

Lisa believes a problem to be special if its index (within a chapter) is the same as the page number where it’s located. Given the details for Lisa’s workbook, can you count its number of special problems?

Lisa’s Workbook

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This brute force solution iterates over all pages in the final book keeping track of the page(offset) and chapter it is on. There can only be one special problem per page and therefore I check if there is any problem that would match the criteria.

Solution:

def findPages(N, K, P):
    cnt = 0
    offset = 1
    for chapter in P:
        pages = (chapter + K -1)/K
        for idx in xrange(pages):
            if offset >= (idx * K)+1 and offset <= min((idx+1)*K, chapter):
                cnt += 1
            offset += 1

    return cnt

if __name__ == '__main__':
    N, K = map(int, raw_input().split())
    P = map(int, raw_input().split())
    print findPages(N, K, P)

Twitter, Facebook

To learn more about solving Coding Challenges in Python, I recommend these courses: Educative.io Python Algorithms, Educative.io Python Coding Interview.