# Fraction to Float Strings

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 takes `constant` time if we want to divide and save `100` values in a string. We find can find every substring of string in O(N2) time where `N` is 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:

1. 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 = ``
Note: We don’t consider Quotient here because we will consider quotients after decimal point.
Quotient List = `[]`
After dividing Numerator becomes `10` and denominator remains `7`.

Step-2 :

Quotient = integer value of `(10/7) => 1`
Remainder = `3`
Remainder List = `[1,3]`
Quotient List = ``
After dividing Numerator becomes `30` and denominator remains `7`.

Step-3 :

Quotient = integer value of `(30/7) => 4`
Remainder = `2`
Remainder List = `[1,3,2]`
Quotient List = `[1,4]`
After dividing Numerator becomes `20` and denominator remains `7`.

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 becomes `60` and denominator remains `7`.

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 becomes `40` and denominator remains `7`.

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 becomes `50` and denominator remains `7`.

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 = {0};
char quotient;
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;
int firstValue = num/den;
num -= firstValue * den;

int remPos = {0};
int remainders = {0};
char quotient;
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;
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.