Minimum number of hops required to traverse an integer array from start to end

Determine the minimum number of hops required to traverse an integer array from start to end, where the value at each position/index denotes the max permissible jump you can make to the right.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numArray = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
            Console.WriteLine("Minimum number of hops required to traverse from start to end = " + GetMinimumHops(numArray));
        }

        public static int GetMinimumHops(int[] numArray)
        {
            int startIndex = 0, hopCount = 0;
            while (startIndex < numArray.Length - 1)
            {
                if (numArray[startIndex] > 0)
                {
                    startIndex = GetMaxVicinityIndex(numArray, startIndex);
                    hopCount++;
                }
                if (startIndex < numArray.Length - 1 && numArray[startIndex] <= 0)
                {
                    return -1;
                }
            }
            return hopCount;
        }

        public static int GetMaxVicinityIndex(int[] numArray, int index)
        {
            int maxVal = 0, maxIndex = 0;
            for (int i = index + 1; i < (index + 1) + numArray[index]; i++)
            {
                if (i == numArray.Length - 1)
                {
                    return numArray.Length - 1;
                }
                if (i == index + 1)
                {
                    maxVal = numArray[i];
                    maxIndex = i;
                }
                else if (maxVal <= numArray[i])
                {
                    maxVal = numArray[i];
                    maxIndex = i;
                }
            }
            return maxIndex;
        }
    }
}

Output
=======
Minimum number of hops required to traverse from start to end = 3
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

One Response to Minimum number of hops required to traverse an integer array from start to end

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s