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

Sort by

recency

|

3281 Discussions

|

  • pavelbaitalik
     + 0 comments

    Solution i have tried::: Java 

    public static int jumpingOnClouds(List<Integer> c) {
// Write your code here
int jump=0,temp=0,k=0;

       for(int j=k;j<c.size();j++){

     if( c.get(j)==0){
        temp++;
     }
    if (c.get(j)==1)
    {
        k=j;
         jump+=temp/2;
        temp=0;
        jump++;


    }
       }

         if (c.get(c.size()-1)==0 && c.get(c.size()-2)==0) {
           jump++;
       }
    return jump;
}

  • 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;
}

  • yashdeora98294
     + 0 comments

    Here is problem solution in Python, Java, C++, C and Javascript - https://programmingoneonone.com/hackerrank-jumping-on-the-clouds-problem-solution.html

  • Hyper_Meero
     + 0 comments
    int jumpingOnClouds(vector<int> c) {
    int jumps = 0;
    int i = 0;
    
    while (i < c.size() - 1) {
        if (i + 2 < c.size() && c[i + 2] == 0) {
            i += 2;
        } else {
            i += 1;
        }
        jumps++;
    }
    
    return jumps;
}

  • gschoen
     + 0 comments

    In hindsight, this is just a straight application of the greedy algorithm Just make 2 jumps if you can. I wasn't sure of that so I treated this as a dynamic programming problem.

    #define BIGNUM 1000000000

int jumpingOnClouds(int c_count, int* c) {
    int n = c_count;
    int dp[n];
    dp[n-1] = 0;
    if (c[n-2]) dp[n-2] = BIGNUM;
    else dp[n-2] = 1;
    for (int i = n-3; i >= 0; --i) {
        if (c[i]) {
            dp[i] = BIGNUM;
            continue;
        }
        int step1 = 1 + dp[i+1];
        int step2 = 1 + dp[i+2];
        if (step1 > step2) step1 = step2;
        dp[i] = step1;
    }
    return dp[0];
}