Google Interview Question
SDETsCountry: United States
Interview Type: Phone Interview
awesome, this works. I tried a random number like 58/2828 and it returns 0.0205(091937765205) which is the correct value considering the original output would have been 0.02050919377652050919377652050919.
One small modification I would do to the above code is to replace
real = a / b
remain = a % b
with
real, remain = divmod(a,b)
It does not return 0.5(0). The (0) is easy to add though :)
loganwol: 0.0205(091937765205) is not the correct output :) The correct output for 58/2828 should be 0.0(205091937765)
def rational(a,b):
i = True
y = str(a/b)+'.'
c = a % b
l = []
m = []
while i:
d = c*10/b
c = (c*10)%b
if c ==0:
i = False
l.append(str(d))
l.append('(0)')
else:
if c in m:
i = False
j = m.index(c)
l.append(')')
l.insert(j,'(')
else:
m.append(c)
l.append(str(d))
for i in l:
y += i
print y
return
int part1 = numerator/denominator;
numerator = (numerator%denominator);
int rem = ((numerator*10)/denominator);
String part2 = "";
Set<Integer> mods = new LinkedHashSet<Integer>();
while(!mods.contains(rem)) {
mods.add(rem);
numerator = (numerator*10) % denominator;
rem = ((numerator*10)/denominator);
}
for(Integer i : mods) {
if(i==rem) {
part2 += "(";
}
part2 += i;
}
part2+=")";
System.out.println(part1+"."+part2+"");
Hold on a second. I am not sure I understand or fully agree with the premise of this question. How is 2 divided by 4 0.5 with 5 repeating? And why does this question claim that all rational numbers end with a repeating section? BTW, a number ending in x.9 with 9 repeating is not a decimal representation for a rational number.
All rationals do have repeating decimals. But you are right about 2,4. That should be 0.5(0)
You can add as many 0's as you want to every number in existence but that doesn't mean it actually has a repeating value.
Solution in C#
public static string Partition(decimal num, decimal denum)
{
string str = (num / denum).ToString();
string st = str.ToString().Split(',')[1];
string liste = string.Empty;
foreach (var item in st)
{
if (liste.Contains(item))
{
break;
}
liste += item;
}
return string.Format("{0}.({1})",str.Split(',')[0],liste);
}
This is the solution I provided first until I was given the example of this -
1, 29 = 0.0344827586206896551724137931034482758620689655172413793103448275862068965517241379310344827586206896551724137931
which would be 0.(03448275862068965517241379310)
notice that will there is a 0, it is not followed by a 3 but instead by a 6. In proposed that instead we find the index of the next 0, take the substring from 0 to index - 1 and then take the substring from index to string1.Length -1 and compare the two. If they were equal we have the string otherwise we repeat the same.
How about this?
PHP CODE:
find_repeat(13,29);
function find_repeat($n, $m){ // format:n/m
$part1 = floor($n/$m);
$part2 = "";
$hash_array = array();
$hash_array = array_pad($hash_array, $m, false);
$x = $n % $m;
$j = 0;
while(true)
{
if($hash_array[$x] !== false)
break;
else
{
$hash_array[$x] = $j;
$part2 .= floor(10*$x/$m);
$x = 10*$x%$m;
}
$j++;
}
$part2 = substr($part2,0,$hash_array[$x]).'('.substr($part2,$hash_array[$x]).')';
echo $part1.'.'.$part2;
return;
}
void PrintRational(int num, int denum) {
std::string str = std::to_string(num / denum) + ".";
std::unordered_map<int, int> hash;
int repeat_index = 0;
while (true) {
num = (num % denum) * 10;
auto repeat = hash.find(num);
if (repeat != hash.end()) {
repeat_index = repeat->second;
break;
}
hash[num] = str.size();
str += std::to_string(num / denum);
}
std::cout << str.substr(0, repeat_index)
<< "(" << str.substr(repeat_index) <<")"
<< std::endl;
}
Inspired by Kalias, the following scala code simulates division by hand. i.e., multiply residual by 10 then repeatedly compute mod and residual while tracking mod. One bug fix from Kalias' code is to determine where repeat starts. String is used to keep the repeat parts, rather than int, which will overflow for large denominators. Result is tested against big decimal.
import scala.collection.mutable._
def Rational(numerator:Int, denominator:Int):String = {
var residual = numerator % denominator
var repeat = ""
var mods = List[Integer]()
while(!mods.contains(residual)) {
mods ::= residual
repeat = repeat + (if (residual*10<denominator) "0" else (residual*10)/denominator)
residual = residual*10%denominator
}
//repeat starts at the position where we first see the repeated residual
var lead = 0
while (mods.reverse(lead)!=residual) lead+=1
(numerator/denominator)+s".${repeat.take(lead)}(${repeat.drop(lead)})"
}
val n = 1
val d =29
println(Rational(n,d))
val bn = new java.math.BigDecimal(n)
val bd = new java.math.BigDecimal(d)
println(bn.divide(bd, d*3, RoundingMode.DOWN))
The solution for this question is knowing the repetition of quotient.
For example, 1/3 is 0.33333, so it would be 0.(3)
If we see detail of this:
1/3 = 0, remainder :1
1 * 10 -> 10/3 -> 3, remainder :1
1 * 10 -> 10/3 -> 3, remainder: 1 (Now, we can know that same quotient is detected, since
this is decimal places based number, actually, if you detect same quotient + remainder combo, you come to know that there will be repetition)
public static String divisionToString(int num1, int num2){
int quotient = num1 / num2;
int remains = num1 % num2;
if (remains == 0) {
return String.valueOf(quotient);
}
StringBuilder remainder = new StringBuilder(quotient + ".");
remains *= 10;
Map<String, Integer> cache = new HashMap<>();
int position = 2;
while(remains != 0) {
int q = remains / num2;
remains = remains % num2;
String key = q+","+remains;
if (cache.containsKey(key)) { // Repition happens
int prePosition = cache.get(key);
String temp = remainder.toString();
return temp.substring(0, prePosition) + "(" + temp.substring(prePosition, position) + ")";
}
remainder.append(q);
cache.put(key, position++);
remains *= 10;
}
return remainder.toString();
}
static String rationalNumber(int numerator, int denominator){
ArrayList<Integer> allNumer = new ArrayList<Integer>();
ArrayList<Integer> quotient = new ArrayList<Integer>();
String result = "";
int num = (numerator % denominator) * 10;
while( num != 0 ){
if( allNumer.contains(num) )
break;
allNumer.add(num);
quotient.add(num/denominator);
num = ( num % denominator ) * 10;
}
for(int i = 0; i < quotient.size(); i++ )
result += quotient.get(i);
if( num == 0 ){
result = Integer.toString(numerator/denominator) + '.' + result + "(0)";
System.out.println(result);
return result;
}
result = Integer.toString(numerator/denominator) + '.' + result.substring(0, allNumer.indexOf(num) ) + '(' + result.substring( allNumer.indexOf(num), result.length() ) + ')';
System.out.println(result);
return result;
}
public static void fn(int i, int j) {
double d = (double) i / (double) j;
String[] split = Double.toString(d).split("\\.");
String decimalPart = split[1];
StringBuilder repeatingSection = new StringBuilder();
for (char letter : decimalPart.toCharArray()) {
repeatingSection.append(letter);
if (decimalPart.replaceFirst(repeatingSection.toString(), "").matches("[" + repeatingSection + "]*")) {
split[1] = repeatingSection.toString();
break;
}
if (!decimalPart.replaceFirst(repeatingSection.toString(), "").contains(repeatingSection)) {
split[1] = repeatingSection.substring(0, repeatingSection.length() - 1);
break;
}
}
System.out.println(split[0] + "." + "(" + split[1] + ")");
}
solution in ruby
def decimals(nr, dr)
r = nr % dr
quotient = []
remainders = {}
loop do
break if r == 0 || !!remainders[r]
remainders[r] = quotient.length
r = r * 10
while r < dr
r = r*10
quotient << 0
end
quotient << r/dr
r = r % dr
end
if r == 0
"#{quotient.join}(0)"
else
"#{quotient[0...remainders[r]].join}(#{quotient[remainders[r]..-1].join})"
end
end
nr, dr = gets.strip.split(" ").map(&:to_i)
puts "#{nr/dr}.#{decimals(nr,dr)}"
In contrast to all solutions posted so far, my solution doesn't use any auxiliary data structure to keep track of repetitions. Therefore, no dynamic memory allocation occurs behind the scenes.
The solution uses properties of integer numbers to detect the moments where the brackets must be open and closed.
#include <cstdlib>
#include <iostream>
int gcd(int m, int n) {
return n == 0 ? m : gcd(n, m % n);
}
unsigned factor_out(int& y, int base) {
unsigned exponent = 0;
while (y % base == 0) {
++exponent;
y /= base;
}
return exponent;
}
void print(int m, int n) {
if ((m < 0 && n > 0) || (m > 0 && n < 0))
std::cout << '-';
m = std::abs(m);
n = std::abs(n);
int const a = m / n;
int r = m % n;
int d = gcd(r, n);
r /= d;
n /= d;
int y = n;
unsigned const prefix = std::max(factor_out(y, 2), factor_out(y, 5));
unsigned period = 1;
if (y != 1) {
for (int x = 10 % y; x != 1; x = (10 * x) % y)
++period;
}
std::cout << a << '.';
for (unsigned i = 0; i < prefix + period; ++i) {
if (i == prefix)
std::cout << '(';
r = 10 * r;
std::cout << r / n;
r = r % n;
}
std::cout << ")\n";
}
The loop on x above is computing period: the multiplicative order of 10 modulo y. This part of the code has complexity O(y) and O(sqrt(y)) algorithms exist to compute this value.
In any case, optimizing this part of the code will not decrease the overall complexity of the code as a whole. Therefore, I preferred to keep it simple.
(function() {
'use strict';
var divide = function(num, den) {
var left = 0;
var leftObj = {};
var i = 0;
var decimalStr = '';
if (den === 0) {
return 0;
}
left = num % den;
var integer = Math.floor((num + 0.1) / den);
while (leftObj[left] === undefined) {
leftObj[left] = i;
left = left * 10;
decimalStr += Math.floor((left + 0.1) / den);
left = left % den;
i++;
}
decimalStr = decimalStr.substr(0, leftObj[left]) + '(' + decimalStr.substr(leftObj[left]) + ')';
return integer + '.' + decimalStr;
};
var numerator = 3;
var denominator = 13;
console.log(divide(numerator, denominator));
})();
import java.util.regex.Pattern;
public class reminder
{
public static void main(String args[])
{
int a= 22;
int b = 7;
int c= a/b;
float d= (float)a/(float)b;
String e = String.valueOf(d);
String[] k =e.split(Pattern.quote("."));
System.out.println(c+".("+k[1]+")");
}
}import java.util.regex.Pattern;
public class reminder
{
public static void main(String args[])
{
int a= 22;
int b = 7;
int c= a/b;
float d= (float)a/(float)b;
String e = String.valueOf(d);
String[] k =e.split(Pattern.quote("."));
System.out.println(c+".("+k[1]+")");
}
}
public static void divide(int a, int b)
{
int quotient = a / b;
int rem = a % b;
int[] hash = new int[b];
for (int i = 0; i < b; i++)
{
hash[i] = -1;
}
int i = 0;
StringBuilder decimals = new StringBuilder();
boolean isRepeating = true;
while (rem != 0 && hash[rem] == -1)
{
hash[rem] = i;
i++;
rem *= 10;
decimals.append(rem / b);
rem = rem % b;
if (rem == 0)
{
isRepeating = false;
break;
}
}
String output = String.valueOf(quotient)+".";
if (isRepeating)
{
int repIndex = hash[rem];
String decimalStr = decimals.toString();
output = output + decimalStr.substring(0, repIndex) + "(" + decimalStr.substring(repIndex) + ")";
}
else
{
output = output + decimals.toString() + "(0)";
}
System.out.println(a + "/" + b + " = " + output);
System.out.println("--------------------------------------------");
}
There's a mistake in the seconds example, 2/4 is not 0.(5) but simply 0.5.
Here I'll just assume the nominator is smaller, since calculating the decimals is the interesting part (the modification is trivial either way). Using python:
def dec(a, b):
decimals = []
seen = []
while True:
if a in seen:
index = seen.index(a)
print "".join(map(str, decimals[:index])) + "(" + "".join(map(str, decimals[index:])) + ")"
break
seen.append(a)
a *= 10
div = a//b
decimals.append(div)
a -= div*b
if a == 0:
print "".join(map(str, decimals))
break
#!/usr/bin/python -tt
import sys
import re
from decimal import *
def is_num(num):
m = re.match(r"^\d*\.?\d*$", num)
if m is None:
print "not number! "
sys.exit(0)
def div_show(num, div):
if Decimal(div) != 0 :
result = str( Decimal(num)/Decimal(div)).split(".")
if len(result) >1:
print result[0]+".("+result[1]+")"
else:
print result[0]+".(0)" ## e.g 1/1, 2389/2389
else:
print "can't divide by zero!"
def main():
if len(sys.argv) <3:
print "enter two number"
else:
is_num(sys.argv[1])
is_num(sys.argv[2])
div_show(sys.argv[1], sys.argv[2])
if __name__ == '__main__':
main()
---------testing--------
$ python qa2.py
enter two number
$ python qa2.py 1
enter two number
$ python qa2.py sdfsdfs
enter two number
$ python qa2.py sdfsdfs sdfsdf
not number!
$ python qa2.py 1234 1234
1.(0)
$ python qa2.py 1234 1233
1.(000811030008110300081103001)
$ python qa2.py 1234 1235
0.(9991902834008097165991902834)
I have included some output to understand what the code does but this seems like a pretty quick solution:
#!/usr/bin/python
x = 1
y = 7
l = []
s = ''
c = 0
mod = x%y # division for the fist decimal
for c in range(20): # number of decimals to scan
mod = mod*10 # new numerator
div = mod/y # result mod/y
mod = mod%y # next numerator
s += str(div)
l.append(s)
if (div == 0): # break if division has no modulo
break
print s
print l
found = 0
for k in range(1,len(l)):
print l[k][:len(l[k])/2], " ", l[k][len(l[k])/2:]
if (l[k][:len(l[k])/2] == l[k][len(l[k])/2:]):
print "FOUND"
found = k
break
if (found==0): # no repetition found, probably s.th. like 1/2
print "Result: ", float(x)/float(y)
else:
print "Result: ", x/y, '. (', l[found/2], ")"
#include<vector>
#include<iostream>
using namespace std;
void decimal(int rem, int divisor);
int main() {
int n,d;
cin>>n>>d;
cout<<n/d<<".";
decimal(n%d,d);
}
void decimal(int rem, int divisor) {
vector<int> hash(divisor,-1);
vector<int> decimal;
while(hash[rem]==-1) {
decimal.push_back((rem*10)/divisor);
hash[rem]=decimal.size()-1;
rem=(rem*10)%divisor;
}
for(int i=0;i<hash[rem];i++)
cout<<decimal[i];
cout<<"(";
for(int i=hash[rem];i<decimal.size();i++) {
cout<<decimal[i];
}
cout<<")"<<endl;
}
public class DecimalRepresentaionOfRational {
int numerator;
int denominator;
int quotient;
boolean hasRepeatPattern = false;
int repetitionStart = -1, repetitionEnd = -1;
DecimalRepresentaionOfRational(int numerator, int denominator){
this.numerator = numerator;
this.denominator = denominator;
}
// assume positive
/*
* 22/7
* > 3. 1/7
* > 3.1 3/7
* > 3.14 2/7
* 2 6/7
* 8 4/7
* 5 5/7
* 7 1/7
*
*
* 1/17
* 0.05 15/17
*
*/
void evaluateAndOutput(){
int residual;
int currentQuotient;
quotient = (int) Math.floor(((double) numerator)/denominator);
residual = numerator % denominator;
List<Integer> residuals = new LinkedList<Integer>();
Map<Integer,Integer> residualVsDigits = new HashMap<Integer,Integer>();
boolean done = (residual == 0);
if(!done){
residuals.add(residual);
}
while(!done){
System.out.println("DEBUG: " + residual);
residual = residual*10;
if(residual == 0){
break;
} else if(residual < denominator){
//List<Integer> result = new LinkedList<Integer>();
residualVsDigits.put(residual/10,0);
//result.add(0);
residuals.add(residual);
} else {
currentQuotient = (int) Math.floor(((double) residual)/denominator);
residualVsDigits.put(residual/10,currentQuotient);
residual = residual % denominator;
residuals.add(residual);
}
if(residualVsDigits.containsKey(residual)){
done = true;
hasRepeatPattern = true;
for(int i = 0; i < residuals.size(); i++){
int r = residuals.get(i);
if(r == residual){
if(repetitionStart==-1){
repetitionStart = i;
} else {
repetitionEnd = i-1;
}
}
}
}
}
System.out.println("DEBUG: " + residuals);
System.out.println("DEBUG: " + hasRepeatPattern + " " + repetitionStart + " " + repetitionEnd);
System.out.print( numerator + "/" + denominator + " = " + quotient);
if(residualVsDigits.size() != 0){
System.out.print(".");
}
for(int i = 0; i < residuals.size(); i++){
int r = residuals.get(i);
if(r != 0){
if(hasRepeatPattern){
if(i == repetitionStart){
System.out.print("(");
}
}
System.out.print(residualVsDigits.get(r));
if(hasRepeatPattern){
if(i == repetitionEnd){
System.out.print(")");
break;
}
}
}
}
System.out.println();
}
public static void main(String[] args){
int[] testcaseNumerator = {4 , 2 , 1, 22 , 1 , 1 };
int[] testcaseDenominator = {2 , 4 , 3, 7, 3000, 37};
for(int i = 0; i < 6; i++){
DecimalRepresentaionOfRational wrapper = new DecimalRepresentaionOfRational(testcaseNumerator[i],testcaseDenominator[i]);
wrapper.evaluateAndOutput();
}
}
}
void print_rational(int num, int den)
{
int left = 0;
std::vector<int> v;
boost::unordered_map<int, int> seen;
left = num / den;
int i = 0;
num -= (left*den);
num *= 10;
while (seen.find(num) == seen.end())
{
int d = num / den;
v.push_back(d);
seen[num] = i;
++i;
num -= d*den;
num = num * 10;
}
int p = seen[num];
std::cout << left << ".";
for (auto i = 0; i < p; ++i) std::cout << v[i];
std::cout << "(";
for (auto i = p; i < v.size(); ++i) std::cout << v[i];
std::cout << ")" << std::endl;
}
Solution in Python:
- Anonymous August 19, 2014