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); }
    } 
    } 

[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.

Leave a Reply

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