Fraction to Float

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 go through the best online coding classes and 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(N^{2}) time where N is the length of the string. Also, we can check the presence in O(N^{2}) time for every single substring. So this takes a total of O(N^{4}) time to find a solution. As we can see this takes a total of O(N^{4}) 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.
> 1) We know the decimal portion repeats itself when a remainder repeats.
> 2) So we’ll check if any remainder repeats and will note it’s the last position in the quotient.
> 3) After we note it, we finish the process of division as now quotient will repeat itself if it goes on.
> 4) 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.
> 5) 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 becomes 10 and denominator remains 7.

Step-2 :

> Quotient = integer value of (10/7) => 1
> Remainder = 3
> Remainder List = [1,3]
> Quotient List = [1]
> 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[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(")");
          }

      }
    }

Previous post Find Maximum
Next post Students Roll Number

Leave a Reply

Your email address will not be published. Required fields are marked *