Project Euler #26: Reciprocal cycles

Sort by

recency

|

40 Discussions

|

  • + 0 comments

    is there a way to see the testcases inputs? I don't why my code is failing one of the test cases..

  • + 0 comments

    // c# using System;

    public class Program { static int FindCycle(int n) { int[] seen = new int[n]; seen[1] = 1; int m = 1; int i = 2;

        while (true)
        {
            m *= 10;
            int p = m % n;
            if (p == 0)
                return 0;
            if (seen[p] != 0)
                return i - seen[p];
            seen[p] = i;
            i++;
            m = p;
        }
    }
    
    public static void Main(string[] args)
    {
        int[] ans = new int[10001];
        int[] cycleLength = new int[10001];
        ans[2] = 3;
        cycleLength[2] = 1;
        ans[3] = 3;
        cycleLength[3] = 1;
    
        for (int i = 4; i <= 10000; i++)
        {
            int p = FindCycle(i);
            if (p > cycleLength[ans[i - 1]])
            {
                ans[i] = i;
                cycleLength[i] = p;
            }
            else
            {
                ans[i] = ans[i - 1];
                cycleLength[i] = cycleLength[i - 1];
            }
        }
    
        int t = int.Parse(Console.ReadLine());
        for (int _ = 0; _ < t; _++)
        {
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(ans[n - 1]);
        }
    }
    

    }

  • + 6 comments
    #python
    def countofdigits(n):
        c=1
        res=set()
        while c<n:
            c=c*10
        while True:
            rem=c %n
            c=rem*10
            if rem==0:
                return 0
            if rem not in res:
                res.add(rem)
            else:
                break
        return len(res)
    
    m=0
    num=0
    result=['L', '0', 'V', 'E']
    for x in range(3, 10000):
        c=countofdigits(x)
        if c>m:
            m=c
            num=x
        result.append(num)
    t=int(input())
    for x in range(t):
        n=int(input())
        print(result[n])
                
        
    
  • + 0 comments

    100% divide will calculate the reccurance , by long division method by dividing 100* > n

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    
    small_frac = []
    
    def divide(n):
        nume = {1: 10, 2:100, 3:1000, 4:10000, 5: 100000}
        d = nume[len(str(n))]
        divq, rep = {}, '0'*(len(str(n))-1)
        l = len(rep)
        while True:
            d1 = d // n
            rep = rep + str(d1)
            d1 = d - n*d1
            d1 = d1 * 10
            #print(d1, l)
            if d1 in divq: 
                return(len(rep[divq[d1]:-1]))
            elif d % n == 0:
                return(0)
            divq[d1] = l
            d, l = d1, l+1
            
                
    def dec_frac():
        lastval = 0
        for i in range(2, 10001):
            val = divide(i)
            if val > lastval:
                small_frac.append(i)
                lastval = val
    
    dec_frac()
    
    #print(small_frac)
    
    def search(n, l, r, a):
        if l == r:
            if n <= a[l]:
                return(a[l-1])
            return(a[l])
        m = (l+r)//2
        if n <= a[m]:
            return(search(n, l, m, a))
        else:
            return(search(n, m+1, r, a))
         
    for a0 in range(int(input())):
        print( search(int(input()), 0, len(small_frac)-1, small_frac) )
    
  • + 0 comments

    Explanation for this simple problem:

    recurring_digits function: This function calculates the span of recurring digits in the decimal expansion of 1/n. It first removes factors of 2 and 5, then iteratively multiplies the remainder by 10 and takes the remainder after division by n until a recurring cycle is detected.

    answers list: list is used to store the maximum recurring digit numbers for each index. It is initialized with four zeros, and the code iterates through numbers from 3 to 10^4 to populate this list.

    Loop for finding maximum recurring digit numbers: The loop iterates through numbers from 3 to 10^4, calculates the recurring digits for each number using the recurring_digits function, and updates the maximum recurring digit number and count accordingly.

    User input processing: The code then takes user input for the number of test cases and the specific values for which it needs to find the maximum recurring digit numbers. It prints the results accordingly.