|
Given an integer N, the task is to print all proper fractions such that the denominator is less than or equal to N.
Proper Fractions: A fraction is said to be a proper fraction if the numerator is less than the denominator.
Examples:
Input: N = 3
Output: 1/2, 1/3, 2/3
Input: N = 4
Output: 1/2, 1/3, 1/4, 2/3, 3/4
Approach:
Traverse all numerators over [1, N-1] and, for each of them, traverse over all denominators in the range [numerator+1, N] and check if the numerator and denominator are coprime or not. If found to be coprime, then print the fraction.
Below is the implementation of the above approach:
C++14
#include <bits/stdc++.h>
using namespace std;
void printFractions(int n)
{
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (__gcd(i, j) == 1) {
string a = to_string(i);
string b = to_string(j);
cout << a + "" + b << ", ";
}
}
}
}
int main()
{
int n = 3;
printFractions(n);
return 0;
}
|
Java
class GFG{
static void printFractions(int n)
{
for(int i = 1; i < n; i++)
{
for(int j = i + 1; j <= n; j++)
{
if (__gcd(i, j) == 1)
{
String a = String.valueOf(i);
String b = String.valueOf(j);
System.out.print(a + "" +
b + ", ");
}
}
}
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
public static void main(String[] args)
{
int n = 3;
printFractions(n);
}
}
|
Python3
def printfractions(n):
for i in range(1, n):
for j in range(i + 1, n + 1):
if __gcd(i, j) == 1:
a = str(i)
b = str(j)
print(a + '/' + b, end = ", ")
def __gcd(a, b):
if b == 0:
return a
else:
return __gcd(b, a % b)
if __name__=='__main__':
n = 3
printfractions(n)
|
C#
using System;
class GFG{
static void printFractions(int n)
{
for(int i = 1; i < n; i++)
{
for(int j = i + 1; j <= n; j++)
{
if (__gcd(i, j) == 1)
{
string a = i.ToString();
string b = j.ToString();
Console.Write(a + "" +
b + ", ");
}
}
}
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
public static void Main(string[] args)
{
int n = 3;
printFractions(n);
}
}
|
Javascript
<script>
const printFractions = (n) => {
for (var i = 1; i < n; i++) {
for (var j = i + 1; j <= n; j++) {
if(__gcd(i, j) == 1){
let a = `${i}`;
let b = `${j}`;
document.write(`${a}/${b}, `)
}
}
}
}
const __gcd = (a, b) => {
if(b == 0){
return a;
}else{
return __gcd(b, a % b);
}
}
let n = 3;
printFractions(n);
</script>
|
Time Complexity: O(N2 log N)
Auxiliary Space: O(1)
|
