We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Lisa's Workbook
  5. Discussions

Lisa's Workbook

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • sb_renderpass
    6 years ago+ 8 comments

    I realised that each page can have at most one special problem, and that the minimum number of special problems is always 1 (chapter 1, page 1, problem 1).
    So I got the bound: (1 <= answer <= total pages)
    Or more generally: (1 <= answer <= total pages <= total problems)
    Basically my algorithm loops over every page and checks if the page number lies within the problem number range of that page. Here's my Python solution:

    N, K = map(int, raw_input().split())
    T = map(int, raw_input().split())
    
    cnt = 0 # special problems
    i = 0   # chapter number
    j = 1   # page number
    m = 1   # problem number
    
    while i < N:
        if m <= j and j <= min(m + K - 1, T[i]):
            cnt += 1
        j += 1
        m += K
        if m > T[i]: # next chapter
            i += 1
            m = 1
    print cnt
    
    73|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature