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!

# FRACTION

Last Updated on April 6, 2022 by Ria Pathak

### CONCEPTS USED:

Greedy algorithm.

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()
{
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”

1. Sheetal says:

unable to see the code !