Cuente fracciones cuadradas perfectas de una array dada

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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *