LeetCode Q166: Fraction to Recurring Decimal

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)".

Solution:

Consider how the long division is done. Compute residual and result of division in each iteration. In the meantime keep track the residual using hash map in order to detect repeating pattern. Basically, the repetition happens when the same residual value appears again. Need to consider some boundary case such as "-2147483648", "-1"

 

	class Solution {
	public:
	string fractionToDecimal(int _nu, int _de) {
	long nu=long(_nu);
	long de=long(_de);
	string res;
	bool pts=false;
	bool repeat=false;
	unordered_map<int, int> myMap;
	if((nu<0&&de>0) || (nu>0&&de<0)){
	res=res+string("-");
	}
	nu=abs(nu);
	de=abs(de);
	long residual=nu;
	if(nu==0)
	return string("0");
	while(residual!=0){
	long s = residual/de;
	residual=residual-s*de;
	res=res+to_string(s);
	if(!pts&&residual!=0){
	res=res+string(".");
	pts=true;
	}
	if(residual==0)
	break;
	if(myMap[residual]!=0&&s!=0){
	repeat=true;
	break;
	}
	myMap[residual]=res.length();
	residual*=10;
	}
	if(repeat){
	res.insert(myMap[residual], "(");
	res=res+string(")");
	}
	return res;
	}
	};

view raw Q166FractiontoRecurringDecimal.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	string fractionToDecimal(int _numerator, int _denominator) {
	string res;
	long numerator = _numerator;
	long denominator = _denominator;
	res=numerator*denominator<0? string("-"):res;
	numerator=abs(numerator);
	denominator=abs(denominator);
	if(numerator>denominator){
	long r = numerator/denominator;
	res = res+to_string(r);
	numerator = numerator - denominator*r;
	}else
	res = res+string("0");
	if(numerator!=0)
	res+=string(".");
	unordered_map<long, long> myHash;
	vector<long> tmpR;
	vector<long> tmpNu;
	while(numerator!=0){
	int r = numerator*10/denominator;
	if(myHash[numerator]!=0){
	for(int i=0; i<tmpR.size(); i++){
	if(tmpNu[i]==numerator)
	res = res + string("(")+to_string(tmpR[i]);
	else
	res = res + to_string(tmpR[i]);
	}
	res = res + string(")");
	return res;
	}else{
	myHash[numerator] = 1;
	tmpR.push_back(r);
	tmpNu.push_back(numerator);
	}
	numerator = numerator*10 - denominator*r;
	}
	for(int i=0; i<tmpR.size(); i++)
	res = res+to_string(tmpR[i]);
	return res;
	}
	};

view raw Q166Rnd2.cpp hosted with ❤ by GitHub