CareerCup

Maybe i didn't make clear why multiplying by 10 is needed

if

ghy/abdc = 0.ABDCUDEG..

then

ghy * 10 / abdc = A.BDCUDEG..

so we extracting A here

@anonymous1 :
what will happen in cases of 0.449672
or 0.0007711983.
i think you r wrong

What about these two examples don't work ?

Hey anonymous, you are awesome!!! Nice solution

Why make it super complex when the entire decimal portion can be obtained as below:
double x = N/D;
double decimal = x - (int) x;

I think the main part of the problem is not how we extract the decimal portion, but rather how we can find a pattern within the decimal part. I think the easiest way to find the pattern is to rely on suffix trees; check my solution below.

@anonymous: WOW!! thanks for visualizing the schoolbook division ))

Generating digits of decimal expansion can be done,
e.g., using the following simple algorithm:

void div_periodic(int num, int denom) {

    int div = num / denom;
    int mod = num % denom;
    printf("%d.", div); // print integer part
    num = mod;
    int niters = 100;
    std::vector< int > digits;

    while(niters--) {
    num *= 10; // num is always smaller than denom
    int n_zeros = 0;
    while(num < denom) { // add the required number of zeros
        num *= 10; n_zeros++;
        digits.push_back(0);  
    }
    div = num / denom; // div is always a single digit
    mod = num % denom;

    digits.push_back(div); // add the next digit
    num = mod;
    if(num == 0)
        break;
    }
}

However, now it comes to the two main problems:

how to find where the period starts ?
how to find the length of the period ?

I think interviewers that ask such questions do not really understand the problem themselves because there is a significant amount of math behind it.

Consuling wikipedia, we find out that whenever
a denominator has factors of the form 2^a*5^b,
the resulting reciprocal is eventually periodic
but has a non-repeating sequence of digits of size max(a,b).

Now assume we know where the period starts.
The next problem is that a smaller period can be the part of larger
ones. For example, consider a decimal expansion of

1414147 / 999999999

which is 0.(001414147)

so there is no trivial way to detect it unless we know
what the maximal period of a fraction could be.

Again consulting wikipedia, we find that
the period of a reciprocal 1 / p is the order of 10 in Z/Zp,
given by Euler totient function, and is at most (p-1).

This suggests that we have to compute the first (p-1) digits
of decimal expansion of 1/p to find the period!!!

Is there another way ?

> how to find where the period starts ?
> how to find the length of the period ?

Standard cycle-finding algorithm, e.g., Floyd's.

> Is there another way ?

Basically we're computing a discrete logarithm. The naive algorithm isn't the fastest, but no one knows how to compute discrete logs in poly-time (i.e., in the number of digits of the modulus).

my algo above clearly explains when the period will start.

hey anonymous .. ur sol is clean and good. and btw it allows to know the decimal part easily