Finding Repeating part of fraction (a/b) and print only repeating integers as String in java?

user_15591112 0
Viewed 683

I'm solving a problem of fraction,

  1. if the fraction part is repeating, print the only repeating integers as String.
  2. if the fraction part is not repeating, print upto 4 digits after decimal.
  3. if the fraction output is simple print it directly as string.

E.g.

a) 1/3 = 0.3333... , here 3 is recurring, so need to print only 0.3. b) 5/2 = 2.5 -- Simple Math. c) 22/7 = 3.14287, here 14287 is repeating, so need to print 3.14287

Can you please help, the solution should have O(k) time complexity and space complexity

public String fractionToDecimal(int numerator, int denominator) {
    StringBuilder tem = new StringBuilder();
    long q = numerator / denominator;

    return tem.append(q);
}
math java
1 Answers

This question is quite complicated. You need to know quite a few advanced concepts to fully understand why it is so.

Binary vs. Decimal

The notion '1 divided by 3 repeats the 3 endlessly' only works if you presuppose a decimal rendering system. Think about it: Why does '10' come after '9'? As in, why did 'we' decide not to have a specific symbol for the notion 'ten', and instead this is the exact point on the number line 'we' decided to go for two digits, the first digit and the zero digit written next to each other? That's an arbitrary choice, and if you delve into history, humans made this choice because we have 10 fingers. Not all humans made this choice, to be clear: Sumerians had unique digits all the way up to 60, and this explains why there are 60 seconds in a minute, for example. There are remote tribes using 6, 3, and even weirder number systems.

If you want to spend some fun math time, go down the rabbithole on wikipedia reading about exotic number systems. It's mesmering stuff, a fine way to spend an hour (or two, or ten!)

Imagine a number system for aliens that had only 3 fingers total. They'd count:

Human Alien
0     0
1     1
2     2
3     10
4     11
5     12
6     20
8     21
9     22
10    30

Their number system isn't "weird" or "bad". Just different.

However, that number concept goes both ways: When you write, say, "1 divided by 4 = 0.25", that 25 is also in 'decimal' (the name for a number system that has 10 digits, like what most humans on the planet earth like to use).

In human, 1 divided by 10 is 0.1. Easy, right?

Well, in '3-finger alien', one divided by three is... 0.1.

Not 0.1 repeating. Nono. Just 0.1. It fits perfectly. In their number system, one divided by ten is actually quite complicated, where it is ridiculously simple in ours.

Computers are aliens too. They have 2 fingers. Just 0 and 1, that's all. A computer counts: 0 1 10 11 100 101 110 111 and so on.

An a / b operation that repeats in decimal may not repeat in binary. Or it may. Or a number that doesn't repeat in decimal may repeat in binary (1/5 repeats endlessly in binary, in decimal, it's just 0.2, easy).

Given that computers don't like counting in decimal, any basic operation is an instant 'loser' - you can no longer answer the question if you even write double or float anywhere in your code here.

But it requires knowledge of binary and some fairly fundamental math to even know that.

Solution strategy 1: BigDecimal

NOTE: I don't think this is the best way to go about it, I'd go with strategy 2, but for completeness...

Java has a class baked into the core library called java.math.BigDecimal that is intended to be used when you don't want any losses. double and float are [A] binary based, so trying to use them to figure out repeating strides is completely impossible, and [B] silently round numbers all the time to the nearest representable number. You get rounding errors. Even 0.1 + 0.2 isn't quite 0.3 in double math.

For these reasons, BigDecimal exists, which is decimal, and 'perfect'.

The problem is, well, it's perfect. In basis, dividing 1 by 3 in BigDecimal math is impossible - an exception occurs. You need to understand the quite complicated API of BigDecimal to know about how to navigate this issue. You can tell BigDecimal about exactly how much precision you're okay with.

So, what you can do:

  • Convert your divider and dividend into BigDecimal numbers.
  • Configure these for 100 digits after the comma precision.
  • Divide one by the other.
  • Convert the result to a string.
  • Analyse the string to find the repeating stride.

That algorithm is technically still incorrect - you can have inputs that have a repetition stride that is longer than 100 characters, or a division operation that appears to have a repeating stride when it actually doesn't.

Still, for probably every combination of numbers up to 100 or so you care to throw at it, the above would work. You can also choose to go further (more than 100 digits), or to write an algorithm that tries to find a repeat stride with 100 digits, and if it fails, that it just uses a while loop to start over, ever incrementing the # of digits used until you do find that repeating stride in the input.

You'll be using many methods of BigDecimal and doing some fairly tricky operation on the resulting string to attempt to find the repetition stride properly.

It's one way to solve this problem. If you would like to try, then read this and have fun!

Solution Strategy 2: Use math

You can use a mathematical algorithm to derive the next decimal digit given a divisor and dividend. This isn't so much computer science, it's purely a mathematical exercise, and hence, don't search for 'java' or 'programming' or whatnot online when looking for this.

The basic gist is this:

1/4 becomes the number 0.25, how would one derive that? Well, had you multiplied the input by 10 first, i.e. calculate 10/4, then all you really need to do is calculate in integral math. 4 fits into 10 twice, with some left over. That's where the 2 comes from.

Then to derive the 5: Take the left-over (4 fits into 10 twice, and that leaves 2), and multiply it again by 10. Now calculate 20/4. That is 5, with nothing left over. Great, that's where the 5 comes from, and we get to conclude that there is no need to continue. It's zeroes from here on out.

You can write this algorithm in java code. Never should it ever mention double or float (you immediately fail the exercise if you do this). a / b, if both a and b are integral, does exactly what you want: Calculates how often b fits into a, tossing any remainder. You can then obtain the remainder with some more simple math:

int dividend = 1;
int divisor = 4;
List<Integer> digits = new ArrayList<>();

// you're going to have to think about when to end this loop
System.out.print("The digits are: 0.");
while (dividend != 0 && digits.size() < 100) {
   dividend *= 10;
   int digit = dividend / divisor;
   dividend -= (digit * divisor);
   digits.add(digit);
   System.out.print(digit);
}

I'll leave the code you'd need to write to find repetitions to you. You can be certain it repeats 'cleanly' when your divisor number ends up being a divisor value you've seen before. For example, when doing 1/3, going through this algorithm:

First loop through:

  • dividend (1) is multiplied by 10, becomes 10.
  • dividend is now integer-divided by the divisor (3), producing the digit 3.
  • We determine what's left: the digit times the divisor is 9, so 9 of those 10 have been used up, leaving the 1. We set dividend to 1.

As you can see, nothing actually changed: The dividend is still 1 just like it was at the start, therefore all loops through go like this, producing an endless stream of 3 values, which is indeed the correct answer.

You can maintain a list of dividends you've already seen. e.g. by storing them in a Set<Integer>. Once you hit a number you've already seen, you can just stop printing: You've started the repetition.

This algorithm has the considerable benefit of always being correct.

So what do I do?

I think your teacher wants you to figure out the second one, and not to delve into the BigDecimal API.

This is an awesome exercise, but more about math than programming.

user_7686440
Related