Monday, April 27, 2009

The hopping grasshopper

I came across this quiz from the Internet (credits go to whoever prepared this question) and thought of giving it a try. The question is as follow:

A grasshopper is hopping forth and back in the field. Each time it hops, the distance is equal to the number of the hop. So for the first hop the distance is one unit, the second hop the distance is two units etc. However, the grasshopper would not hop back if it will otherwise land beyond the origin where it has started.

Your task is to write a program to determine whether the grasshopper can be N units from where it begins if it makes N hops, and the number of hopping patterns.

The following diagram shows that for 4 hops, there is only one possible hopping pattern.

Input: An integer not more than 25.
Output: The number of hopping patterns or zero if no such hop pattern is possible for the given input number.

Sample Input: 4
Sample Output: 1
Here's my solution to the trivia. It may be perfect, it may be not. Please feel free to drop a comment if you feel there is a simpler way to solve this.

public static int hop(int numberOfHops){
int hopCount = 1;
int unitCount = 0;
int pattern = 0;
int currentIndex = 0;

if (numberOfHops < 1 || numberOfHops > 25) {
//returns a 0 if the supplied input is more than 25
//or less than 1
return 0;
}

while (hopCount <= numberOfHops) {
unitCount = unitCount + 1;
currentIndex = currentIndex + unitCount;
if (currentIndex > numberOfHops) {
//bounces back the grasshopper if it is about to
//hop out of bound from the current spot
currentIndex = currentIndex - (unitCount*2);
}
if (hopCount == numberOfHops) {
if (currentIndex == numberOfHops) {
pattern++;
}
}
hopCount++;
}
return pattern;
}

0 comments:

Post a Comment