HackerRank ‘Jumping on the Clouds’ Solution

Short Problem Definition:

Emma is playing a new mobile game involving clouds numbered from 1 to n. There are two types of clouds, ordinary clouds and thunderclouds. The game ends if Emma jumps onto a thundercloud, but if she reaches the last cloud, she wins the game!

Link

Jumping on the Clouds

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Theoretically your solution can depend on the fact that the win condition is guaranteed, but I don’t like such solutions. Here I present a semi-DP approach that keeps track of the optimal number of jumps it takes to reach each cloud.

Solution:

[rust]
use std::io;
use std::cmp;

fn get_number() -> u32 {
let mut line = String::new();
io::stdin().read_line(&mut line).ok().expect("Failed to read line");
line.trim().parse::<u32>().unwrap()
}

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
io::stdin().read_line(&mut line).ok().expect("Failed to read line");
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn calculate_jumping(a: Vec<u32>, n: usize) -> u32{
let mut v = vec![100; n];
v[0] = 0;

for i in 1..n {
//println!("{} {} {:?}", i, a[i], v);
if a[i] == 1 {
continue;
}

if i == 1 {
v[i] = v[i-1] + 1;
} else {
v[i] = cmp::min(v[i-1], v[i-2]) + 1;
}
}

v[n-1]
}

fn main() {
let n = get_number() as usize;
let a = get_numbers();

println!("{}", calculate_jumping(a, n) );
}
[/rust]


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin