Dadas dos arrays arr1[] y arr2[] de longitud N que contienen Numerador y Denominador de N fracciones respectivamente, la tarea es contar el número de fracciones de la array que es un cuadrado perfecto de una fracción .
Ejemplos:
Entrada: arr1[] = {3, 25, 49, 9}, arr2[] = {27, 64, 7, 3}
Salida: 2
Explicación:
(arr1[0] / arr2[0]) = (3 / 27 ) = (1 / 9) = (1 / 3) 2
(arr1[1] / arr2[1]) = (25 / 64) = (5 / 8) 2
(arr1[0] / arr2[0]) y (arr1[1] / arr2[1]) son fracciones cuadradas perfectas. Por lo tanto, la salida requerida es 2.Entrada: arr1[] = {1, 11, 3, 9}, arr2[] = {9, 11, 5, 1}
Salida: 3
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable cntPerfNum para almacenar el recuento de fracciones cuadradas perfectas.
- Recorra las arrays y para cada elemento de la array, compruebe si el valor de (arr1[i] / GCD(arr1[i], arr2[i]) ) y (arr2[i] / GCD(arr1[i], arr2[ i]) ) es un cuadrado perfecto o no. Si se determina que es cierto, incremente el valor de cntPerfNum en 1 .
- Finalmente, imprima el valor de cntPerfNum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the GCD
// of two numbers
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
bool 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 fractions
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 Code
int 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 approach
import 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 code
public 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 numbers def GCD(a, b): # If b is 0 if (b == 0): return a return GCD(b, a % b) # Function to check if N # is perfect square def 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 # fractions def 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 code if __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 approach
using 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 code
public 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 numbers
function GCD(a,b)
{
// If b is 0
if (b ==0 ) {
return a;
}
return GCD(b,a%b);
}
// Function to check if N
// is perfect square
function 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 fractions
function 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>
Producción:
2
Complejidad de tiempo: O(N * log(M)), donde M es el elemento máximo de ambas arrays.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA