Project Euler Problem 26

This week's puzzle comes from project euler, see the description of the puzzle here:
http://projecteuler.net/index.php?section=problems&id=26

Analysis

How do we find when a cycle occurs in the decimal representation of a unit fraction? The expansion of 1 divided by 14 is 0.0(714285), Let's see step by step what happens while expanding 1 divided by 14:

Note: dividend = previous remainder * 10

dividend	divisor	result	remainder
10	14	0	10
100	14	7	2
20	14	1	6
60	14	4	4
40	14	2	12
120	14	8	8
80	14	5	10
100	14	7	2
20	14	1	6
60	14	4	4
40	14	2	12
...	...	...	...

Note that the cycle re-started when the same remainder appeared (see numbers in red). I recommend you to try 1/17 = 0.(0588235294117647) to double check this behavior.

Here are a some additional facts that can help to find the solution:

1. If the remainder at some point is 0, the decimal representation of the unit fraction is finite.
2. For a unit fraction 1/d, the length of the cycle must be smaller than d, since there are at most d-1 possible remainders. As soon as we find a repeater remainder, we find the cycle.
3. Because the problem just requires d smaller than 1000, we can start verifying values of d in decreasing order. If at some point we find a cycle of length x, we know we do not need to check values of d smaller than or equal to x, because those values of d cannot create a larger cycle.

With all this in mind, here is the code I came up with.

 1 package cspuzzles;
 2 
 3 public class ProjectEuler26 {
 4     // We use this array to map from remainder to the first position where the
 5     // remainder was found. For example, for 1/14 = 0.0(714285)
 6     // indexOfRemainder[10] = 0;
 7     // indexOfRemainder[2] = 1;
 8     // indexOfRemainder[6] = 2;
 9     // indexOfRemainder[4] = 3;
10     // indexOfRemainder[12] = 4;
11     // indexOfRemainder[8] = 5;
12     // In this problem, we just need up to 1000 entries.
13     private int[] indexOfRemainder = new int[1000];
14 
15     private void solve(){
16         int d = 999; // we inspect values of d in decreasing order
17         int longestCycle = 1; // minimum value of d to inspect
18         int solution = -1;
19         int index = 0;
20         int remainder = 0;
21 
22         // This loop is to check possible values of d.
23         // When d is smaller than the longestCycle, there is no need
24         // to continue checking
25         while(d > longestCycle){
26             cleanMap();
27             // the initial numerator is 1, and this is also the
28             // initial remainder because we are working with unit fractions
29             remainder = 1;
30             index = 0;
31             // This loop is to find the cycle for a given value of d
32             while(remainder != 0) {
33                 // compute new remainder
34                 remainder = (remainder * 10) % d;
35                 // check if we have found a cylce
36                 if(remainder == 0){
37                     // there is no cycle
38                 }
39                 else if(indexOfRemainder[remainder] == -1){
40                     // first time we find this remainder
41                     indexOfRemainder[remainder] = index;
42                 }
43                 else {
44                     // THE CYCLE!!!
45                     // the length of the cycle is the current index minus
46                     // the index where the current remainder was previouly found
47                     longestCycle = index - indexOfRemainder[remainder];
48                     solution = d;
49                     remainder = 0; // break the while
50                 }
51                 index++;
52             }
53             d--;
54         }
55         System.out.println("Solution: " + solution);
56         System.out.println("Cycle length: " + longestCycle);
57     }
58 
59     private void cleanMap(){
60         for(int i = 0; i < indexOfRemainder.length; i++)
61             indexOfRemainder[i] = -1;
62     }
63 
64     public static void main(String[] args){
65         new ProjectEuler26().solve();
66     }
67 }

Do you like this kind of puzzles? Share your opinion in the comments.