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.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Jumping on the Clouds
  5. Discussions

Jumping on the Clouds

  • wdkaye
     + 0 comments

    We already know this input has a solution, therefore there can't be any consecutive '1's in the input. Worst case, a '1' 2 cells ahead forces us to short-jump but then we're guaranteed a long-jump. We can use this to solve the problem faster:

    // Assumptions:
// - c always has a winning solution, which means:
//   - c[0] and c[n-1] must be zero
//   - c does not contain any consecutive 1s
//   - minimum number of jumps is at best (n-1)/2, at worst...
//     - shortest worst case is n=5, c[2] = 1, jumps = 3
//   - worst-case input has '1's on every third entry, forcing single jumps
int jumpingOnClouds(vector<int> c) {
    // TODO validate input

    int hopCount = 0;
    int i = 0;
    while( (i+2) < c.size() ) {
    
        // if c[2] == 1 hop1 and hop2, else hop2
        // this solves the whole problem in O(n)
        if( c[i+2] == 1 ) {
            hopCount += 2;
            i += 3;
        }
        else {
            hopCount += 1;
            i += 2;
        }
    }
    
    // Last hop - there is another cell in front of us and no more 1s.
    if( (i+1) < c.size() ) {
        hopCount++;
    }
    
    return hopCount;
}