# Determine total number of ways of reaching a destination

Question:

One of Scotland Yard’s most wanted criminal (Mister X) is on the run and needs to reach a certain destination safely. There are three modes of transport available for him - By air, by train or by cab. With air travel, he can go from station i to station i+3. Using a train would make him reach station i+2 when starting from i and by taxi he could go to the next station (i+1).

Now, clearly there can be multiple ways of travelling between two stations. Thus, you need to help him find out the total number of ways of reaching station N from station 0. Since the number of ways can be very large output the answer mod 109 +7.

Input Specification:

The first line contains the number of test cases, T. This is followed by T lines each containing an integer N, the station ID.

Output Specification:

Print T lines, each line having the corresponding test case's output.

Sample Input:

2 3 4

Sample Output:

4 7

Constraints:

1 <= T <= 100000

2 <= N <= 107

My code to be optimized:

import java.io.BufferedReader;
import java.io.IOException;
public class Solution {
public static void main(String[] args) throws IOException
{
short ways[]=new short[testCases],i=0;
int stationId;
while(testCases!=0)
{
ways[i++] = (short)(getWays(stationId)%(10^9 +7));
testCases--;
}
for(int k:ways)
System.out.println(k);
}
static int getWays(int n)
{
int sum = 1,i=1;
while(i<=n)
{
sum+=(i-1);
i++;
}
return sum;
}
}

-
You should only change an edit for improvement of formatting only if any meaning in your question was lost. In this case, there wasn't any information lost, so I rolled back the edit. – syb0rg Mar 29 '14 at 19:48
Your sample input does not adhere to the input specification? – 200_success Mar 29 '14 at 22:08
Clarification: In the description it says: Since the number of ways can be very large output the answer mod xxxx. Is the xxxx 10-to-the-power-of-9-plus-7, or is it 10-xor-9-plus-7 ? – rolfl Mar 29 '14 at 22:12
Please do not change the code in the question after it has been answered, as it invalidates existing answers. – 200_success Mar 30 '14 at 6:44

Although this is not related to optimization, it looks like you could improve some of the ways you use loops. If you're using a counter, chances are you should use a for loop:

for (int i = number; i > 0; i--) { /*...*/ }


This works best if the loop counter initialization is pretty short. But if it's too long and should remain on its own line, then instead have a while loop that updates the counter within the statement:

int i; // some long initialization here instead...

while (i-- > 0) { /*...*/ }


First, I want to mention that you should use whitespace between operators and keywords for readability. You use it in some places, but you should use it everywhere for consistency.

Second, non-empty code blocks should have the opening curly brace at the end of the line, not on the following line. This is referenced in Google Java Style.

Instead of decrementing testCases within the loop:

while(testCases!=0)
{
ways[i++] = (short)(getWays(stationId)%(10^9 +7));
testCases--;
}


have it done in the while loop statement:

while (testCases-- > 0) {
ways[i++] = (short)(getWays(stationId)%(10^9 +7));
}


Instead of incrementing i within the loop:

while(i<=n)
{
sum+=(i-1);
i++;
}


make it a for loop:

// move the initialization of i into the loop

for (int i = 1; i <= n; i++) {
sum += (i-1);
}


On another note, this:

short ways[]=new short[testCases],i=0;


should be on separate lines:

short ways[] = new short[testCases];
short i = 0;


Although they're of the same type, i is hard to see since it's crammed right next to ways[].

-