Last Updated on March 28, 2022 by Ria Pathak
Concepts Used
Strings
Difficulty Level
Hard
Problem Statement (Simplified):
Print the decimal output of the fraction of two given numbers and enclose the repeating part in decimal places in brackets. For example, for a given input of 2 and 3, it’s fraction is 2/3. Its decimal representation would be 0.6666 where 6 repeats indefinitely, so we cover 6 in brackets and puts output as 0.(6).
See original problem statement here
Test Case
Input:
2
1 3
94 36
Output:
0.(3)
2.6(1)
Explanation:
Case-1:
Given in test case, 1/3 when converted to floating value gives 0.3333333 as output, as 3 repeats indefinitely, we put 3 in bracket and print 0.(3) as the answer.
Case-2:
Given in test case, 94/36 when converted to floating value give 2.611111 as output, as 1 repeats itself in floating number, so we put 1 in brackets. So we print 2.6(1) as the answer.Solving Approach :
Bruteforce Approach:
1) We can continuously divide and save quotients in a string.
2) After saving values in a string, we check for repeating patterns in the whole string.
3) After we have found a repeating pattern, we print the pattern quotient until the first appearance of the repeating pattern. Then we print the repeating pattern in brackets.
4) Calculating string takesconstanttime if we want to divide and save100values in a string. We find can find every substring of string in O(N2) time whereNis the length of the string. Also, we can check the presence in O(N2) time for every single substring. So this takes a total of O(N4) time to find a solution. As we can see this takes a total of O(N4) time to calculate the whole answer, but this approach is very inefficient, so we use a different efficient approach to solve this problem.
Efficient Approach:
-
If a fraction is non-repeating, any of its remainders will come 0 on repetitive division.
-
We know the decimal portion repeats itself when a remainder repeats.
-
So we’ll check if any remainder repeats and will note it’s the last position in the quotient.
-
After we note it, we finish the process of division as now quotient will repeat itself if it goes on.
-
Now print the integer part, a decimal point, non-repeating decimal part, an opening bracket, repeating decimal part, and a closing bracket if there are any recurring decimal places.
-
If there is no recurring decimal portion, just print the integer part, decimal point and fraction.
-
Example
- Let’s consider Numerator = 22 Denominator=7 .
- We repeatedly divide until we encounter any repeating Remainder, for that we take care for every Remainder we encounter. Also we store quotients we recieve after decimal point.
NOTE: We add 0 after Remainder and saves in numerator after every division. If after division, numerator is still less than denominator, we add a ‘0’ in quotient.
Step-1 :
Quotient = integer value of
(22/7) => 3
Remainder =1
Remainder List =[1]
Note: We don’t consider Quotient here because we will consider quotients after decimal point.
Quotient List =[]
After dividing Numerator becomes10and denominator remains7.
Step-2 :
Quotient = integer value of
(10/7) => 1
Remainder =3
Remainder List =[1,3]
Quotient List =[1]
After dividing Numerator becomes30and denominator remains7.
Step-3 :
Quotient = integer value of
(30/7) => 4
Remainder =2
Remainder List =[1,3,2]
Quotient List =[1,4]
After dividing Numerator becomes20and denominator remains7.
Step-4 :
Quotient = integer value of
(20/7) => 2
Remainder =6
Remainder List =[1,3,2,6]
Quotient List =[1,4,2]
After dividing Numerator becomes60and denominator remains7.
Step-5 :
Quotient = integer value of
(60/7) => 8
Remainder =4
Remainder List =[1,3,2,6,4]
Quotient List =[1,4,2,8]
After dividing Numerator becomes40and denominator remains7.
Step-6 :
Quotient = integer value of
(40/7) => 5
Remainder =5
Remainder List =[1,3,2,6,4]
Quotient List =[1,4,2,8,5]
After dividing Numerator becomes50and denominator remains7.
Step-7 :
Quotient = integer value of
(50/7) =>; 7
Remainder =1
Remainder List =[1,3,2,6,4,1]
Quotient List =[1,4,2,8,5,7]
We can see 1 is repeated in Remainder list, so our fraction repeats at position at which 1 first appeared in Remainder list. As we can see 1 appeared at index 0, so we’ll put all values from index 0 to current index in Quotient List in bracket.
So, our final answer becomes integer value + Quotients, i.e.
3.(142857).
Solutions
#include <stdio.h>
int main()
{
int num,den;
scanf("%d%d", &num,&den);
int firstValue = num/den;
num -= firstValue * den;
int remPos[1000000] = {0};
char quotient[15];
int recurr = 0;
int rem = num % den ;
int quoPos = 0;
remPos[rem] = 1;
int i = 0;
if(rem!=0)
i = 1;
for( ; rem && !recurr; i++){
int temp = rem * 10;
while(temp<den){
if(remPos[temp] > 0){
rem = temp;
quotient[quoPos++] = '0';
recurr = 1;
break;
}
temp *= 10;
quotient[quoPos++] = '0';
}
if(recurr)
break;
num = temp;
rem = num % den;
quotient[quoPos++] = num/den + '0';
if(rem == 0){
break;
}
else{
if(remPos[rem] > 0){
recurr = 1;
break;
}
else{
remPos[rem] = i+1;
}
}
}
quotient[quoPos] = '\0';
if(!recurr){
if(i == 0 )
printf("%d",firstValue);
else
printf("%d.%s",firstValue,quotient);
}else{
printf("%d.",firstValue);
for(int k=0; k<remPos[rem]-1; k++)
printf("%c",quotient[k]);
printf("(");
for(int k=remPos[rem]-1; k<quoPos; k++){
printf("%c",quotient[k]);
}
printf(")\n");
}
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int num,den;
cin>>num>>den;
char dec[100000];
int firstValue = num/den;
num -= firstValue * den;
int remPos[1000000] = {0};
int remainders[1000000] = {0};
char quotient[15];
bool recurr = false;
int rem = num % den ;
int quoPos = 0;
remPos[rem] = 1;
int i = 0;
if(rem!=0)
i = 1;
for( ; rem && !recurr; i++){
int temp = rem * 10;
while(temp<den){
if(remPos[temp] > 0){
rem = temp;
quotient[quoPos++] = '0';
recurr = true;
break;
}
temp *= 10;
quotient[quoPos++] = '0';
}
if(recurr)
break;
num = temp;
rem = num % den;
quotient[quoPos++] = num/den + '0';
if(rem == 0){
break;
}
else{
if(remPos[rem] > 0){
recurr = true;
break;
}
else{
remPos[rem] = i+1;
}
}
}
quotient[quoPos] = '\0';
if(!recurr){
if(i == 0 )
cout<<firstValue;
else
cout<<firstValue<<"."<<quotient;
}else{
cout<<firstValue<<".";
for(int k=0; k<remPos[rem]-1; k++)
cout<<quotient[k];
cout<<"(";
for(int k=remPos[rem]-1; k<quoPos; k++){
cout<<quotient[k];
}
cout<<")";
}
cout<<endl;
}
import java.util.*;
import java.io.*;
import java.lang.Math;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc= new Scanner(System.in);
int num = sc.nextInt();
int den = sc.nextInt();
int firstValue = 0;
int rem = 0;
if(den != 0){
firstValue = num/den;
rem = num % den ;
}
num -= firstValue * den;
int remPos[] = new int[1000000];
String quotient = "";
int recurr = 0;
remPos[rem] = 1;
int i = 0;
if(rem!=0)
i = 1;
for( ; rem!=0 && recurr==0 ; i++){
int temp = rem * 10;
while(temp<den){
if(remPos[temp] > 0){
rem = temp;
quotient += '0';
break;
}
temp *= 10;
quotient += '0';
}
if(recurr == 1)
break;
num = temp;
rem = num % den;
quotient += (char)(num/den + (int)('0'));
if(rem == 0){
break;
}
else{
if(remPos[rem] > 0){
recurr = 1;
break;
}
else{
remPos[rem] = i+1;
}
}
}
if(recurr==0){
if(i == 0 )
System.out.print(firstValue );
else
System.out.print(firstValue + "." + quotient);
}else{
System.out.print(firstValue + ".");
for(int k=0; k<remPos[rem]-1; k++)
System.out.print(quotient.charAt(k));
System.out.print("(");
for(int k=remPos[rem]-1; k<quotient.length(); k++){
System.out.print(quotient.charAt(k));
}
System.out.println(")");
}
}
}
[forminator_quiz id="927"]
This article tried to discuss Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.