Given two arrays arr1[] and arr2[] of length N which contains Numerator and Denominator of N fractions respectively, the task is to count the number of fractions from the array which is a perfect square of a fraction.
Examples:
Input: arr1[] = {3, 25, 49, 9}, arr2[] = {27, 64, 7, 3}
Output: 2
Explanation:
(arr1[0] / arr2[0]) = (3 / 27) = (1 / 9) = (1 / 3)2
(arr1[1] / arr2[1]) = (25 / 64) = (5 / 8) 2
(arr1[0] / arr2[0]) and (arr1[1] / arr2[1]) are perfect square fractions. Therefore, the required output is 2.Input: arr1[] = {1, 11, 3, 9}, arr2[] = {9, 11, 5, 1}
Output: 3
Approach: Follow the steps below to solve the problem:
- Initialize a variable cntPerfNum to store the count of perfect square fractions.
- Traverse both the arrays and for each array elements, check if the value of (arr1[i] / GCD(arr1[i], arr2[i])) and (arr2[i] / GCD(arr1[i], arr2[i])) is a perfect square or not. If found to be true then increment the value of cntPerfNum by 1.
- Finally, print the value of cntPerfNum.
Below is the implementation of the above approach:
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;// Function to find the GCD// of two numbersint GCD(int a,int b){ // If b is 0 if (b ==0 ) { return a; } return GCD(b,a%b);}// Function to check if N// is perfect squarebool isPerfectSq(int N){ // Stores square root // of N int x = sqrt(N); // Check if N is a // perfect square if (x * x == N) { return 1; } return 0;}// Function to count perfect square fractionsint cntPerSquNum(int arr1[], int arr2[], int N){ // Stores count of perfect square // fractions in both arrays int cntPerfNum = 0; // Traverse both the arrays for (int i = 0; i < N; i++) { // Stores gcd of (arr1[i], arr2[i]) int gcd = GCD(arr1[i], arr2[i]); // If numerator and denomerator of a // reduced fraction is a perfect square if (isPerfectSq(arr1[i]/ gcd) && isPerfectSq(arr2[i]/ gcd)) { // Update cntPerfNum cntPerfNum++; } } return cntPerfNum;}//Driver Codeint main() { int arr1[]={ 3, 25, 49, 9 }; int arr2[]={ 27, 64, 7, 3 }; int N = sizeof(arr1) / sizeof(arr1[0]); cout<<cntPerSquNum(arr1, arr2, N);} |
Java
// Java implementation of the // above approachimport java.lang.Math; class GFG{ // Function to find the GCD // of two numbers public static int GCD(int a, int b) { // If b is 0 if (b == 0) { return a; } return GCD(b, a % b); } // Function to check if N // is perfect square public static boolean isPerfectSq(int N) { // Stores square root // of N int x = (int)Math.sqrt(N); // Check if N is a // perfect square if (x * x == N) { return true; } return false; } // Function to count perfect square fractions public static int cntPerSquNum(int arr1[], int arr2[], int N) { // Stores count of perfect square // fractions in both arrays int cntPerfNum = 0; // Traverse both the arrays for(int i = 0; i < N; i++) { // Stores gcd of (arr1[i], arr2[i]) int gcd = GCD(arr1[i], arr2[i]); // If numerator and denomerator of a // reduced fraction is a perfect square if (isPerfectSq(arr1[i] / gcd) && isPerfectSq(arr2[i] / gcd)) { // Update cntPerfNum cntPerfNum++; } } return cntPerfNum; }// Driver codepublic static void main(String[] args) { int arr1[] = { 3, 25, 49, 9 }; int arr2[] = { 27, 64, 7, 3 }; int N = arr1.length; System.out.println(cntPerSquNum(arr1, arr2, N));}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation of the# above approach# Function to find the GCD# of two numbersdef GCD(a, b): # If b is 0 if (b == 0): return a return GCD(b, a % b)# Function to check if N# is perfect squaredef isPerfectSq(N): # Stores square root # of N x = (int)(pow(N, 1 / 2)) # Check if N is a # perfect square if (x * x == N): return True return False# Function to count perfect square # fractionsdef cntPerSquNum(arr1, arr2, N): # Stores count of perfect square # fractions in both arrays cntPerfNum = 0 # Traverse both the arrays for i in range(N): # Stores gcd of (arr1[i], arr2[i]) gcd = GCD(arr1[i], arr2[i]) # If numerator and denomerator of a # reduced fraction is a perfect square if (isPerfectSq(arr1[i] / gcd) and isPerfectSq(arr2[i] / gcd)): # Update cntPerfNum cntPerfNum += 1 return cntPerfNum# Driver codeif __name__ == '__main__': arr1 = [ 3, 25, 49, 9 ] arr2 = [ 27, 64, 7, 3 ] N = len(arr1) print(cntPerSquNum(arr1, arr2, N))# This code is contributed by Princi Singh |
C#
// C# implementation of the // above approachusing System;class GFG{ // Function to find the GCD // of two numbers public static int GCD(int a, int b) { // If b is 0 if (b == 0) { return a; } return GCD(b, a % b); } // Function to check if N // is perfect square public static bool isPerfectSq(int N) { // Stores square root // of N int x = (int)Math.Sqrt(N); // Check if N is a // perfect square if (x * x == N) { return true; } return false; } // Function to count perfect // square fractions public static int cntPerSquNum(int []arr1, int []arr2, int N) { // Stores count of perfect square // fractions in both arrays int cntPerfNum = 0; // Traverse both the arrays for(int i = 0; i < N; i++) { // Stores gcd of (arr1[i], arr2[i]) int gcd = GCD(arr1[i], arr2[i]); // If numerator and denomerator // of a reduced fraction is a // perfect square if (isPerfectSq(arr1[i] / gcd) && isPerfectSq(arr2[i] / gcd)) { // Update cntPerfNum cntPerfNum++; } } return cntPerfNum; }// Driver codepublic static void Main(String[] args) { int []arr1 = {3, 25, 49, 9}; int []arr2 = {27, 64, 7, 3}; int N = arr1.Length; Console.WriteLine(cntPerSquNum(arr1, arr2, N));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Function to find the GCD// of two numbersfunction GCD(a,b){ // If b is 0 if (b ==0 ) { return a; } return GCD(b,a%b);}// Function to check if N// is perfect squarefunction isPerfectSq( N){ // Stores square root // of N var x = Math.sqrt(N); // Check if N is a // perfect square if (x * x == N) { return 1; } return 0;}// Function to count perfect square fractionsfunction cntPerSquNum(arr1,arr2,N){ // Stores count of perfect square // fractions in both arrays var cntPerfNum = 0; // Traverse both the arrays for (var i = 0; i < N; i++) { // Stores gcd of (arr1[i], arr2[i]) var gcd = GCD(arr1[i], arr2[i]); // If numerator and denomerator of a // reduced fraction is a perfect square if (isPerfectSq(arr1[i]/ gcd) && isPerfectSq(arr2[i]/ gcd)) { // Update cntPerfNum cntPerfNum++; } } return cntPerfNum;}var arr1 = [ 3, 25, 49, 9 ]; var arr2 = [ 27, 64, 7, 3 ]; var N = 4; document.write(cntPerSquNum(arr1, arr2, N));// This code is contributed by akshitsaxenaa09.</script> |
Output:
2
Time Complexity: O(N * log(M)), where M is the maximum element from both the arrays.
Auxiliary Space: O(1)
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!
