Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
jump_game.cpp File Reference

Jumping Game algorithm implementation More...

#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for jump_game.cpp:

Namespaces

namespace  greedy_algorithms
 for std::vector
 

Functions

bool greedy_algorithms::can_jump (const std::vector< int > &nums)
 Checks whether the given element (default is 1) can jump to the last index.
 
static void test ()
 Function to test the above algorithm.
 
int main ()
 Main function.
 

Detailed Description

Jumping Game algorithm implementation

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. This solution takes in input as a vector and output as a boolean to check if you can reach the last position. We name the indices good and bad based on whether we can reach the destination if we start at that position. We initialize the last index as lastPos. Here, we start from the end of the array and check if we can ever reach the first index. We check if the sum of the index and the maximum jump count given is greater than or equal to the lastPos. If yes, then that is the last position you can reach starting from the back. After the end of the loop, if we reach the lastPos as 0, then the destination can be reached from the start position.

Author
Rakshaa Viswanathan
David Leal

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
71 {
72 test(); // run self-test implementations
73 return 0;
74}
static void test()
Function to test the above algorithm.
Definition jump_game.cpp:57
Here is the call graph for this function:

◆ test()

static void test ( )
static

Function to test the above algorithm.

Returns
void
57 {
58 assert(greedy_algorithms::can_jump(std::vector<int>({4, 3, 1, 0, 5})));
59 assert(!greedy_algorithms::can_jump(std::vector<int>({3, 2, 1, 0, 4})));
60 assert(greedy_algorithms::can_jump(std::vector<int>({5, 9, 4, 7, 15, 3})));
61 assert(!greedy_algorithms::can_jump(std::vector<int>({1, 0, 5, 8, 12})));
62 assert(greedy_algorithms::can_jump(std::vector<int>({2, 1, 4, 7})));
63
64 std::cout << "All tests have successfully passed!\n";
65}
bool can_jump(const std::vector< int > &nums)
Checks whether the given element (default is 1) can jump to the last index.
Definition jump_game.cpp:42
Here is the call graph for this function: