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?
time complexity is O(N)
space complexity is O(1)
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.
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)
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.