use std::time::Instant;

fn cycle_length(n : usize) -> usize {
    let mut cycle = vec![0usize; n];
    let mut length = 0;
    let mut modulus = 1;
    let mut last_modulus : usize;
    loop {
        modulus %= n;

        last_modulus = cycle[modulus];

        if last_modulus != 0 {
            break;
        }
        cycle[modulus] = length;
        length += 1;
        modulus *= 10;
    }
    length - last_modulus
}

pub fn reciprocal_cycles(n : usize) -> usize {
    let mut max = 0;
    let mut longest = 1;

    for i in (1..n).rev() {
        if i < max {
            break;
        }

        let length = cycle_length(i);
        if length > max {
            max = length;
            longest = i;
        }

    }

    longest
}

pub fn main() {
    let now = Instant::now();
    let solution = reciprocal_cycles(1000);
    println!("{} in {:?}", solution, now.elapsed());
}