For the past few months I had been working attempting to solve a challenge per day on HackerRank. I like that site. A couple weeks ago I was introduced to LeetCode. Challenges seem to be more intense and requirements seem to be vaguer. Knowing this, one needs to think and plan the approach / algorithm with greater care and expect to fail unit tests that one would not think off. I just finished a challenge and decided to post in this blog my approach to solving it.
Let’s start with the challenge definition:
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”
I strongly recommend for any person involved in software development 
to take a look at the LeetCode web site (https://leetcode.com/), join and practice their challenges. It is an educational, humbling and rewarding experience.
Following is output from the console in the Eclipse IDE for my submission using the examples:
main >>> numerator: 1
main >>> denominator: 2
main <<< result ==>0.5<==
main >>> numerator: 2
main >>> denominator: 1
main <<< result ==>2<==
main >>> numerator: 2
main >>> denominator: 3
main <<< result ==>0.(6)<==
In my humble opinion, 1 / 2 and 2 / 3 qualify as data for the challenge, while 2 / 1 does not. The statement seems to describe the fraction in string format. No mention of positive or negative input is offered. The input values appear to be integers.
The challenge does offer the following hints:
No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.
Following is Eclipse IDE console output using the hints:
main >>> numerator: 4
main >>> denominator: 9
main <<< result ==>0.(4)<==
main >>> numerator: 4
main >>> denominator: 333
main <<< result ==>0.(012)<==
A nice thing about LeetCode is that when you fail a test, you are provided with details about the failure and the line number in which the code fails. This is quite nice because no one develops code in the dark. HackerRank provides this type of information (I have never looked at it) but they demand a payment in Hackos. Hackos are points you have earned by solving previous challenges. The IDEs that I use (e.g., Eclipse, JavaBeans and Visual Studio) do not require payment of any type when I edit and test my code.
The following output is from the IDE console:
main >>> numerator: 1
main >>> denominator: 214748364
main <<< result ==>0.00(000000465661289042462740251655654056577585848337359161441621040707904997124914069194026549138227660723878669455195477065427143370461252966751355553982241280310754777158628319049732085502639731402098131932683780538602845887105337854867197032523144157689601770377165713821223802198558308923834223016478952081795603341592860749337303449725)<==
Any thoughts on the denominator? Perhaps the following would help:
<<< Integer.MAX_VALUE: 2147483647
The previous number may represent a negative number that when you extract the absolute value (Math.abs()) you may still get a negative number. Like I mentioned, the challenge does not make references to ranges or negative values.
The following output is also interesting:
main >>> numerator: -1
main >>> denominator: -2147483648
main <<< result ==>0.0000000004656612873077392578125<==
The denominator is close to an integer boundary. There was no mention on the number of digits the fractional part may produce. I also ran into the following test case:
“0.0000000046566128904246274025165565405657758584833735916144162104”
“0.00(000000465661289042462740251655654056577585848337359161441621040707904997124914069194026549138227660723878669455195477065427143370461252966751355553982241280310754777158628319049732085502639731402098131932683780538602845887105337854867197032523144157689601770377165713821223802198558308923834223016478952081795603341592860749337303449725)”
The first string corresponds to an incorrect answer that a previous version of my code produced. The entire string is correct, but the repetitive cycle is produced later if one continues with the division operation further. The second string is the correct answer for the test. My current code passed it just by allowing more digits as you will see in the Java code.
My code follows:
import java.util.HashMap;
import java.util.Scanner;
public class Solution {
static String longDivision(long n, long d) {
final int maxDecimals = 1024;
boolean done = false;
String result = “”;
long r = n;
// **** check if result is 0 ****
if (n == 0) {
return “0”;
}
// **** compute integral part ****
result += (n / d);
// **** compute remainder ***
r = n % d;
// **** determine if we are done ****
if (r == 0) {
return result;
}
// **** add decimal point ***
result += “.”;
// **** ****
HashMap<Long, Integer> map = new HashMap<Long, Integer>();
StringBuilder fraction = new StringBuilder(“”);
map.put(r, fraction.length());
// **** compute rest of fractional part ****
for (int i = 0; !done && (i < maxDecimals); i++) {
// **** bring down next digit (multiply by 10) ****
r *= 10;
// **** perform the division ****
fraction.append(r / d);
// **** compute the reminder ****
r = r % d;
// **** determine if we are done ****
if (r == 0) {
done = true;
continue;
}
// **** find (if not found insert) ****
if (map.containsKey(r)) {
// **** ****
int s = map.get(r);
int e = fraction.length();
// **** build the fractional part ****
String as = fraction.substring(0, s);
String bs = “(“;
String cs = fraction.substring(s, e);
String ds = “)”;
fraction.setLength(0);
fraction.append(as);
fraction.append(bs);
fraction.append(cs);
fraction.append(ds);
// **** ****
done = true;
continue;
} else {
map.put(r, fraction.length());
}
}
// **** ****
return result + fraction;
}
static String fractionToDecimal(int numerator, int denominator) {
String result = “”;
// **** take care of the leading negative sign ****
String sign = ((numerator < 0) ^ (denominator < 0)) ? “-” : “”;
if (numerator == 0) {
sign = “”;
}
// **** ****
result = longDivision(Math.abs((long)numerator), Math.abs((long)denominator));
// **** ****
return sign + result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numerator = 0;
int denominator = 0;
boolean done = false;
while (!done) {
System.out.print(“main >>> numerator: “);
try {
numerator = sc.nextInt();
} catch (Exception ex) {
done = true;
continue;
}
System.out.print(“main >>> denominator: “);
denominator = sc.nextInt();
System.out.println(“main <<< result ==>” + fractionToDecimal(numerator, denominator) + “<==”);
}
sc.close();
}
}
As usual, I include a Main() with some test code. A good thing to always do is to develop code using a test driven approach.
As you can see by looking at the code, it reflects changes that were due to the failures on some of the unit tests.
In general one always needs to consider the relationships between the data structure(s) and the algorithm. The HashMap, as suggested, blends with the algorithm quite nicely. I did experiment with Regular Expressions on the results, but decided to follow the hints.
If you have comments or questions on this or any other blog entry, please send me an email.
John
john.canessa@gmail.com