Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on April 6, 2022 by Ria Pathak

CONCEPTS USED:

Greedy algorithm.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT(SIMPLIFIED):

Now Arnab is given a fraction N/D. He is asked to divide the fraction in sum of unique unit fractions where N/D=(1/D1)+(1/D2)+(1/D3)+…+(1/Dn). Now find the value of D1,D2,….,Dn.if (1/Di)=2 then value of Di=1/2, print it in fraction as 1/2 not as floating point number.

See original problem statement here

For Example :

1
2 3

2 6

We know,
2/3=1/2+1/6.

We can't take d1=1 ,since 2/3<1.
when d1=2,we are left with 2/3-1/2 i.e. 1/6.

OBSERVATION:

A fraction is a unit fraction if its numerator is 1 and its denominator is any positive integer.

Every positive fraction can be represented as a sum of unique unit fractions.

SOLVING APPROACH:

Given a fraction nr/dr ,there arise the following cases:

  1. nr
  2. nr=dr
  3. nr >dr

If nr=dr, the fraction reduces to 1 , so the required unit fraction is just 1/1.

If nr>dr, we print nr/dr and recur for (nr%dr,dr) .

If nr>

a. if(dr%nr==0) print 1/(dr/nr),

b. if(dr%nr>0) find ceiling of dr/nr and print it as first fraction

SOLUTIONS:

#include <stdio.h>
     void solve(int nr, int dr) 
    { 
    if (dr == 0 || nr == 0) 
        return; 
    if (dr%nr == 0) 
    { 
        printf("%d ",dr/nr); 
        return; 
    } 
    if (nr%dr == 0) 
    { 
        printf("1/%d ",nr/dr); 
        return; 
    } 
    if (nr > dr) 
    { 
        printf("1/%d ",nr/dr); 
        solve(nr%dr, dr); 
        return; 
    } 

    int n = dr/nr + 1; 
    printf("%d ",n); 
    solve(nr*n-dr, dr*n); 
    }     
    int main()
    {
    // write your code here
    int t;
     scanf("%d",&t);
     while(t--)
    {
    int nr,dr;
    scanf("%d%d",&nr,&dr);
    solve(nr,dr);
    }
    return 0;
    }
#include <bits/stdc++.h>
     using namespace std;
     void solve(int nr, int dr) 
    { 
    if (dr == 0 || nr == 0) 
        return; 
    if (dr%nr == 0) 
    { 
        cout  << dr/nr <<" "; 
        return; 
    } 
    if (nr%dr == 0) 
    { 
        cout << "1/"<<nr/dr<<" "; 
        return; 
    } 
    if (nr > dr) 
    { 
        cout << "1/"<< nr/dr << " "; 
        solve(nr%dr, dr); 
        return; 
    } 

    int n = dr/nr + 1; 
    cout <<  n << " "; 
    solve(nr*n-dr, dr*n); 
    }     
     int main()
    {  


    int t;
    cin>>t;
    while(t--)
    {
    int n,m;
    cin>>n>>m;

    solve(n,m);
    cout<<endl;
    }
    return 0;
    }

import java.util.*;
    class unitfractions { 

      static void printfrac(int nr, int dr) { 
        if (dr == 0 || nr == 0) { 
            return; 
        } 
        if (dr % nr == 0) { 
            System.out.print("1/" + dr / nr); 
            return; 
        } 
        if (nr % dr == 0) { 
            System.out.print(nr / dr); 
            return; 
        } 
        if (nr > dr) { 
            System.out.print(nr / dr + " "); 
            printfrac(nr % dr, dr); 
            return; 
        } 
        int n = dr / nr + 1; 
        System.out.print("1/" + n + " "); 
        printfrac(nr * n - dr, dr * n); }

    public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int nr = sc.nextInt();
            int dr = sc.nextInt();
        printfrac(nr, dr); }
    } 
    } 
def solve(nr, dr):

	if dr == 0 or nr == 0:
		return 

	if dr % nr == 0:
		print(dr // nr, end = " ")
		return

	if nr % dr == 0:
		print("1/", nr//dr, end = " ")
		return

	if nr > dr:
		print("1/", nr//dr, end = " ")
		solve(nr % dr, dr)
		return

	n = dr // nr + 1
	print(n, end = " ")
	solve(nr * n - dr, dr * n)


for _ in range(int(input())):
	n, m = map(int,input().split())
	solve(n, m)
	print()

[forminator_quiz id="1414"]

This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.

One thought on “FRACTION

Leave a Reply

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