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 according to data structures in c++.


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

Previous post DIGIT GAME
Next post PROFIT PRIORITY

Leave a Reply

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