-2

I recently came across an interview question asked by Google and I am not able to find an optimized algorithm to solve this question:

Given 2 numbers a and b. Divide a and b and return result in form of a string.

Example 1

Input: a=100 , b=3
Output: 33.(3)   
Note: (100/3)=33.33333....Here 3 is in brackets because it gets repeated continuously.

Example 2

Input: a=5 , b=10
Output: 0.5

Example 3

Input: a=51 , b=7
Output: 7.(285714)
Note: 51/7 = 7.285714285714285714285714285714......... Here 285714 is in brackets because it is repeating.

It would be great if anyone can think of a time-optimized algorithm for this question. Thank You in advance.

Ayush
  • 2,608
  • 2
  • 22
  • 31
  • Did you check [Stern–Brocot tree](http://en.wikipedia.org/wiki/Stern-Brocot_tree)? – Rahul Tripathi Jun 26 '14 at 09:28
  • 2
    It is not really clear what is the specification and what is your own comments. The problem is what? The division? The number of decimals? The parenthesis formatting? Where did `7.(285714)` come from and what determined the number of decimals? Because they are one sequence, or what? – Lundin Jun 26 '14 at 09:29
  • @n.m. Especially since you'll only get just so many decimals out of your double-precision float... I would imagine you'd need a special floating point library to even get a result string "long enough". – Lundin Jun 26 '14 at 09:40
  • 1
    Who has said something about floats? Not me. – n. m. could be an AI Jun 26 '14 at 09:47
  • @Lundin If you don't understand the problem statement, you fail the interview. Sorry. You can educate yourself [here](http://en.wikipedia.org/wiki/Repeating_decimal). This is elementary school material. – n. m. could be an AI Jun 26 '14 at 10:07
  • @n.m. This will be a tad bit cumbersome to implement without floats. I do understand the problem now, though that involved a lot of reading between the lines. The problem statement is: `Divide a and b and return result in form of a string.`. It is not complete. And I still don't understand what part of it that the OP is having trouble _programming_. – Lundin Jun 26 '14 at 10:50
  • 1
    @Lundin I agree the question is of little to no relevance to SO (though it might be relevant to Google). – n. m. could be an AI Jun 26 '14 at 10:57

2 Answers2

4

You can simply perform long division by hand, which is O(N) on the number of digits -- it's hard to see how you could do better than that.

The only problem with long division is that it would not terminate ever if the fraction is a repeating decimal, but you can easily detect this before starting (the fraction is a repeating decimal iff b has any factors other than 2 and 5). If it is a repeating decimal, you need to keep a list of interim remainders that you have already seen. When you encounter one that you have seen before, you know that you have just found the end of the repeating period.

Jon
  • 428,835
  • 81
  • 738
  • 806
2

You might try to keep track of the last N digits in the quotient (N being equal to the number of the digits in the divisor) and the remainder, once you hit the same combination ( last N digits + remainder) your number sequence is going to repeat (I don't have a hard proof for that, but interview questions aren't supposed to be very hard...)

Ashalynd
  • 12,363
  • 2
  • 34
  • 37
  • +1 for you,Yeah tracking of last N digits seems to be the viable option! – Am_I_Helpful Jun 26 '14 at 09:34
  • But floating point calculations are not that accurate! With 100 and 3, printing as `%.20g` shows `33.333333333333336`, which is not equal to `33.(3)`. – Jongware Jun 26 '14 at 10:20
  • You don't do float division, you do integer division by modulo and note the result and the reminder. – Ashalynd Jun 26 '14 at 12:07