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:
- nr
- nr=dr
- 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.
unable to see the code !