Given two arrays num[] and den[] which denotes the numerator and denominator respectively, the task is to find the count of the unique fractions.
Examples:
Input: num[] = {1, 2, 3, 4, 5}, den[] = {2, 4, 6, 1, 11}
Output: 3
Explanation:
Simplest forms of the fractions
Frac[0] =>
Frac[1] =>
Frac[2] =>
Frac[3] =>
Frac[4] =>Count of Unique Fractions => 3
Input: num[] = {10, 20, 30, 50}, den[] = {10, 10, 10, 10}
Output: 4
Explanation:
Simplest forms of the fractions
Frac[0] =>
Frac[1] =>
Frac[2] =>
Frac[3] =>Count of Unique Fractions => 4
Approach: The idea is to use hash-map to find the unique fractions. To store the fractions such that the duplicates are not there, we convert each fraction to its lowest form.
Below is the implementation of the above approach:
C++
// C++ implementation to find// fractions in its lowest form#include <bits/stdc++.h>using namespace std;// Recursive function to// find gcd of a and bint gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// Function to count the unique// fractions in the given arrayint countUniqueFractions(int num[], int den[], int N){ // Hash-map to store the fractions // in its lowest form map<pair<int, int>, int> mp; // Loop to iterate over the // fractions and store is lowest // form in the hash-map for (int i = 0; i < N; i++) { // for the fractions with numerator as 0, // the fractions 0/2,0/3,0/x should be counted as similar if(num[i] == 0) mp[make_pair(0, 0)] += 1; else { int number, denom; // To find the Lowest form number = num[i] / gcd(num[i], den[i]); denom = den[i] / gcd(num[i], den[i]); // the fractions -1/2 and 1/-2 should be considered similar if(denom < 0) number *= -1; mp[make_pair(number, denom)] += 1; } } return mp.size();}// Driver codeint main(){ int N = 6; // Numerator Array int num[] = { 1, 40, 20, 5, 6, 7 }; // Denominator Array int den[] = { 10, 40, 2, 5, 12, 14 }; cout << countUniqueFractions(num, den, N); return 0;} |
Java
// Java implementation to find // fractions in its lowest form import java.lang.*;import java.util.*;class GFG{ static class pair{ int x, y; pair(int x,int y) { this.x = x; this.y = y; } @Override public int hashCode() { return this.x; } @Override public boolean equals(Object obj) { // If both the object references are // referring to the same object. if(this == obj) return true; // It checks if the argument is of the // type pair by comparing the classes // of the passed argument and this object. // if(!(obj instanceof pair)) return // false; ---> avoid. if(obj == null || obj.getClass() != this.getClass()) return false; // Type casting of the argument. pair geek = (pair) obj; // comparing the state of argument with // the state of 'this' Object. return (geek.x == this.x && geek.y == this.y); } }// Recursive function to // find gcd of a and bstatic int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// Function to count the unique// fractions in the given arraystatic int countUniqueFractions(int num[], int den[], int N){ // Hash-map to store the fractions // in its lowest form Map<pair, Integer> mp = new HashMap<>(); // Loop to iterate over the // fractions and store is lowest // form in the hash-map for(int i = 0; i < N; i++) { // for the fractions with numerator as 0, // the fractions 0/2,0/3,0/x should be counted as similar if(num[i] == 0) { pair tmp = new pair(0, 0); mp.put(tmp, 1); } else { // To find the Lowest form int number = num[i] / gcd(num[i], den[i]); int denom = den[i] / gcd(num[i], den[i]); // the fractions -1/2 and 1/-2 should be considered similar if(denom < 0) number *= -1; pair tmp = new pair(number, denom); mp.put(tmp, 1); } } return mp.size();}// Driver Codepublic static void main (String[] args){ int N = 6; // Numerator Array int num[] = { 1, 40, 20, 5, 6, 7 }; // Denominator Array int den[] = { 10, 40, 2, 5, 12, 14 }; System.out.print(countUniqueFractions(num, den, N));}}// This code is contributed by offbeat |
Python3
from fractions import Fractionfrom collections import defaultdict# Recursive function to find gcd of a and bdef gcd(a, b): if b == 0: return a return gcd(b, a % b)# Function to count the unique fractions in the given arraydef countUniqueFractions(num, den, N): # Dictionary to store the fractions in its lowest form mp = defaultdict(int) # Loop to iterate over the fractions and store its lowest form in the dictionary for i in range(N): # for the fractions with numerator as 0, # the fractions 0/2, 0/3, 0/x should be counted as similar if num[i] == 0: mp[Fraction(0, 1)] += 1 else: number = num[i] // gcd(num[i], den[i]) denom = den[i] // gcd(num[i], den[i]) # the fractions -1/2 and 1/-2 should be considered similar if denom < 0: number *= -1 mp[Fraction(number, denom)] += 1 return len(mp)# Driver codeif __name__ == '__main__': N = 6 # Numerator Array num = [1, 40, 20, 5, 6, 7] # Denominator Array den = [10, 40, 2, 5, 12, 14] print(countUniqueFractions(num, den, N)) |
C#
// C# implementation to find// fractions in its lowest formusing System;using System.Collections.Generic;class GFG{ // Recursive function to find the gcd of a and b static int Gcd(int a, int b) { if (b == 0) return a; return Gcd(b, a % b); } // Function to count the unique fractions in the given arrays static int CountUniqueFractions(int[] num, int[] den, int N) { // Dictionary to store the fractions in their lowest form Dictionary<Tuple<int, int>, int> mp = new Dictionary<Tuple<int, int>, int>(); // Loop to iterate over the fractions and store their lowest // form in the dictionary for (int i = 0; i < N; i++) { // For fractions with numerator as 0, the fractions // 0/2, 0/3, 0/x should be counted as similar if (num[i] == 0) { var key = Tuple.Create(0, 0); if (mp.ContainsKey(key)) mp[key] += 1; else mp[key] = 1; } else { int number, denom; // Find the lowest form by dividing the numerator // and denominator by their GCD number = num[i] / Gcd(num[i], den[i]); denom = den[i] / Gcd(num[i], den[i]); // Fractions like -1/2 and 1/-2 should be considered // similar if (denom < 0) number *= -1; var key = Tuple.Create(number, denom); if (mp.ContainsKey(key)) mp[key] += 1; else mp[key] = 1; } } return mp.Count; } // Driver code static void Main(string[] args) { int N = 6; // Numerator Array int[] num = { 1, 40, 20, 5, 6, 7 }; // Denominator Array int[] den = { 10, 40, 2, 5, 12, 14 }; Console.WriteLine(CountUniqueFractions(num, den, N)); }} |
Javascript
// JavaScript implementation to find// fractions in their lowest form// Recursive function to find gcd of a and bfunction gcd(a, b) { if (b === 0) { return a; } return gcd(b, a % b);}// Function to count the unique// fractions in the given arraysfunction countUniqueFractions(num, den) { // Object to store the fractions // in their lowest form const mp = {}; // Loop to iterate over the // fractions and store their lowest // form in the object for (let i = 0; i < num.length; i++) { // For the fractions with numerator as 0, // the fractions 0/2, 0/3, 0/x should be counted as similar if (num[i] === 0) { mp[`${0}/${0}`] = (mp[`${0}/${0}`] || 0) + 1; } else { let number, denom; // To find the lowest form number = num[i] / gcd(num[i], den[i]); denom = den[i] / gcd(num[i], den[i]); // The fractions -1/2 and 1/-2 should be considered similar if (denom < 0) { number *= -1; } mp[`${number}/${denom}`] = (mp[`${number}/${denom}`] || 0) + 1; } } return Object.keys(mp).length;}// Driver code const num = [1, 40, 20, 5, 6, 7]; const den = [10, 40, 2, 5, 12, 14]; const N = num.length; console.log(countUniqueFractions(num, den, N)); |
Output
4
Time Complexity: O(N*log(MAX)), where N is the size of the array and MAX is the maximum number in the array num and den.
Auxiliary Space: O(N + log(MAX))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
