Project Euler Problem 26: Reciprocal cycles

Problem

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2	=	0.5
1/3	=	0.(3)
1/4	=	0.25
1/5	=	0.2
1/6	=	0.1(6)
1/7	=	0.(142857)
1/8	=	0.125
1/9	=	0.(1)
1/10	=	0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that ¹/₇ has a 6-digit recurring cycle.

Find the value of d < 1000 for which ¹/_d contains the longest recurring cycle in its decimal fraction part.

Solution

Use array to store the index of occurred digits is very efficient. Take 7 as example, each mod is 1,3,2,6,4,5, they are saved as arr[1]=1, arr[3]=2, arr[2]=3, arr[6]=4, arr[4]=5, arr[5]=6. Once you find an arr[i] such that arr[i] != 0, you immediately know the length.

      private static final int LIMIT = 1000;  
      public static void main(String[] args) {  
           int result = 0;  
           int longest = 0;  
           for (int i=2; i<LIMIT; i++){  
                int recurringNum = recurringNum(i);   
                if (recurringNum > longest){  
                     longest = recurringNum;  
                     result = i;  
                }  
           }  
           System.out.println(result);  
      }  
      public static int recurringNum(int num) {  
           int[] arr = new int[num+1];  
           int index = 1;  
           int mod = 1;  
           while(mod != 0 && arr[mod] == 0){  
                arr[mod]=index++;  
                mod = mod * 10 % num;  
           }  
           if (mod == 0){  
                return 0;  
           }  
           return index-arr[mod];  
   }