Simplified Fractions Solution in C++

Problem Description

Ah, the world of fractions! You know, those pesky little numbers that seem to pop up everywhere, like that one friend who always shows up uninvited to your parties. The problem at hand is to find all the simplified fractions between 0 and 1 for a given integer n.

Imagine you’re at a pizza party with n slices of pizza. You want to share those slices with your friends, but you don’t want to be that person who gives out half-eaten slices. So, you need to find all the ways to share the pizza slices in their simplest form. No one wants to deal with fractions like 2/4 when you can just say 1/2, right?

In this problem, you’ll be generating all the fractions numerator/denominator where the numerator is less than the denominator, and they are in their simplest form.

Code Solution


class Solution {
 public:
  vector simplifiedFractions(int n) {
    vector ans;
    for (int denominator = 2; denominator <= n; ++denominator)
      for (int numerator = 1; numerator < denominator; ++numerator)
        if (__gcd(denominator, numerator) == 1)
          ans.push_back(to_string(numerator) + "/" + to_string(denominator));
    return ans;
  }
};

Approach

The approach here is as straightforward as it gets. We loop through all possible denominators from 2 to n and for each denominator, we loop through all possible numerators that are less than the denominator. We check if the greatest common divisor (GCD) of the numerator and denominator is 1, which means they are coprime (or in simplest form). If they are, we add them to our answer list.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n² log n)
Space Complexity	O(n)

Real-World Example

Let’s say you’re at a potluck dinner, and everyone brings a dish. You want to make sure that you can share your dish with everyone without cutting it into awkward portions. If you have 8 pieces of cake, you can share it as 1/8, 1/4, or 3/8, but you wouldn’t want to serve it as 2/8 because that’s just lazy! This problem helps you find all those deliciously simplified ways to share your cake.