CODEWITHSUNDEEP
c++algorithm
Lin Ma
Lin Ma

Reputation: 10159

finding minimum number of jumps

Working on below algorithm puzzle of finding minimum number of jumps. Posted detailed problem statement and two code versions to resolve this issue. I have did testing and it seems both version works, and my 2nd version is an optimized version of version one code, which makes i starts from i=maxIndex, other than continuous increase, which could save time by not iteration all the slots of the array.

My question is, wondering if my 2nd version code is 100% correct? If anyone found any logical issues, appreciate for pointing out.

Problem Statement

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.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

First version code

class Solution {
public:
    int jump(vector<int>& nums) {
        int i = 0, n = nums.size(), step = 0, end = 0, maxend = 0;
        while (end < n - 1) {
            step++;
            for (;i <= end; i++) {
                maxend = max(maxend, i + nums[i]);
                if (maxend >= n - 1) return step;
            }
            if(end == maxend) break;
            end = maxend;
        }
        return n == 1 ? 0 : -1;
    }
};

2nd version code

class Solution {
public:
    int jump(vector<int>& nums) {
        int i = 0, n = nums.size(), step = 0, end = 0, maxend = 0;
        int maxIndex = 0;
        while (end < n - 1) {
            step++;
            for (i=maxIndex;i <= end; i++) {
                if ((i + nums[i]) > maxend)
                {
                  maxend = i + nums[i];
                  maxIndex = i;
                }

                if (maxend >= n - 1) return step;
            }
            if(end == maxend) break;
            end = maxend;
        }
        return n == 1 ? 0 : -1;
    }
};

thanks in advance, Lin

Upvotes: 1

Views: 1010

Answers (1)

Captain Wise
Captain Wise

Reputation: 480

The best way is always to test it. A human cannot always think about special cases but a automated test can cover the most of speciale cases. If you think that your first version works well, you can compare the result of the first with the second one. Here an exemple:

/*
 * arraySize    : array size to use for the test
 * min          : min jump in the array
 * max          : max jump in the array
 */
void testJumps(int arraySize, int min, int max){

    static int counter = 0;
    std::cout << "-----------Test " << counter << "------------" << std::endl;
    std::cout << "Array size : " << arraySize << "   Minimum Jump : " << min << "   Max Jump" << max << std::endl; 
    //Create vector with random numbers
    std::vector<int> vecNumbers(arraySize, 0);
    for(unsigned int i = 0; i < vecNumbers.size(); i++)
        vecNumbers[i] = rand() % max + min;

    //Value of first function
    int iVersion1 = jump1(vecNumbers);

    //Second fucntion
    int iVersion2 = jump2(vecNumbers);

    assert(iVersion1 == iVersion2);

    std::cout << "Test " << counter << " succeeded" << std::endl;
    std::cout << "-----------------------" << std::endl;

    counter++;

}

int main()
{
    //Two test
    testJumps(10, 1, 100);
    testJumps(20, 10, 200);

    //You can even make a loop of test
    //...
}

Upvotes: 1

Related Questions