Cuente las ocurrencias de un elemento en una array de tamaño N * N generada de tal manera que cada elemento sea igual al producto de sus índices

Dados dos enteros positivos N y X , la tarea es contar las ocurrencias del entero X dado en una array cuadrada de longitud N generada de tal manera que cada elemento de la array sea igual al producto de sus índices de fila y columna ( basado en 1 indexación ).

Ejemplos:

Entrada: N = 5, X = 6
Salida: 2
Explicación: 
La array 2D formada es igual a:
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
Hay 2 ocurrencias del elemento X(= 6) en la array generada.

Entrada: N = 7, X = 12
Salida: 4

Enfoque ingenuo: el enfoque más simple es construir la array dada multiplicando los índices de fila y columna para obtener cada elemento de la array. Después de generar la array, imprima el recuento de ocurrencias de X en la array. 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )

Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación de que cada elemento de la array es un producto de 2 números . Entonces, al verificar la cantidad de formas en que X se puede representar como un producto de 2 números y seleccionar los pares que se encuentran en el rango [1, N] , se obtiene el resultado. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos count , para almacenar el recuento de ocurrencias de X en la array generada.
  • Iterar sobre el rango [1, √X] usando la variable i y realizar los siguientes pasos:
    • Si el valor de i divide a X , almacena el cociente obtenido al dividir X entre i en una variable, digamos b .
    • Si el valor de i y b cae en el rango [1, N] , realice los siguientes pasos:
      • Comprueba si i es igual a b o no. Si se determina que es cierto, significa que X es un cuadrado perfecto y que la fila y la columna aparecerán una vez. Por lo tanto, aumente la cuenta en 1 .
      • De lo contrario, significa que ocurrirán dos veces, una vez en una fila y en una columna la otra vez. Por lo tanto, aumente la cuenta en 2 .
  • Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to count the occurrences
// of X in the generated square matrix
int countOccurrences(int N, int X)
{
     
    // Stores the required result
    int count = 0;
 
    //Iterate upto square root of X
    for (int i = 1; i < sqrt(X); i++)
    {
         
        // Check if i divides X
        if (X % i == 0)
        {
             
            // Store the quotient obtained
            // on dividing X by i
            int a = i;
            int b = X / i;
 
            // If both the numbers fall in
            // the range, update count
            if (a <= N && b <= N)
            {
                if (a == b)
                    count += 1;
                else
                    count += 2;
            }
        }
    }
     
    // Return the result
    return count;
}
 
// Driver code
int main()
{
     
    // Given N and X
    int N = 7;
    int X = 12;
     
    // Function Call
    cout << countOccurrences(N, X);
     
    return 0;
}
 
// This code is contributed by mohit kumar 29

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to count the occurrences
  // of X in the generated square matrix
  static int countOccurrences(int N, int X)
  {
 
    // Stores the required result
    int count = 0;
 
    // Iterate upto square root of X
    for (int i = 1; i < Math.sqrt(X); i++) {
 
      // Check if i divides X
      if (X % i == 0) {
 
        // Store the quotient obtained
        // on dividing X by i
        int a = i;
        int b = X / i;
 
        // If both the numbers fall in
        // the range, update count
        if (a <= N && b <= N) {
          if (a == b)
            count += 1;
          else
            count += 2;
        }
      }
    }
 
    // Return the result
    return count;
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Given N and X
    int N = 7;
    int X = 12;
 
    // Function Call
    System.out.println(countOccurrences(N, X));
  }
}
 
// This code is contributed by Kingsh.

Python3

# Python3 program for the above approach
from math import sqrt
 
# Function to count the occurrences
# of X in the generated square matrix
def countOccurrences(N, X):
 
    # Stores the required result
    count = 0
 
    # Iterate upto square root of X
    for i in range(1, int(sqrt(X))+1):
 
        # Check if i divides X
        if X % i == 0:
 
            # Store the quotient obtained
            # on dividing X by i
            a = i
            b = X//i
 
            # If both the numbers fall in
            # the range, update count
            if a <= N and b <= N:
                if a == b:
                    count += 1
                else:
                    count += 2
 
    # Return the result
    return count
 
 
# Driver Code
if __name__ == '__main__':
 
    # Given N and X
    N = 7
    X = 12
 
    # Function Call
    print(countOccurrences(N, X))

C#

// C# program for above approach
using System;
public class GFG
{
 
  // Function to count the occurrences
  // of X in the generated square matrix
  static int countOccurrences(int N, int X)
  {
 
    // Stores the required result
    int count = 0;
 
    // Iterate upto square root of X
    for (int i = 1; i < Math.Sqrt(X); i++) {
 
      // Check if i divides X
      if (X % i == 0) {
 
        // Store the quotient obtained
        // on dividing X by i
        int a = i;
        int b = X / i;
 
        // If both the numbers fall in
        // the range, update count
        if (a <= N && b <= N) {
          if (a == b)
            count += 1;
          else
            count += 2;
        }
      }
    }
 
    // Return the result
    return count;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    // Given N and X
    int N = 7;
    int X = 12;
 
    // Function Call
    Console.Write(countOccurrences(N, X));
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to count the occurrences
// of X in the generated square matrix
function countOccurrences(N, X)
{
     
    // Stores the required result
    var count = 0;
 
    //Iterate upto square root of X
    for (var i = 1; i < Math.sqrt(X); i++)
    {
         
        // Check if i divides X
        if (X % i == 0)
        {
             
            // Store the quotient obtained
            // on dividing X by i
            var a = i;
            var b = X / i;
 
            // If both the numbers fall in
            // the range, update count
            if (a <= N && b <= N)
            {
                if (a == b)
                    count += 1;
                else
                    count += 2;
            }
        }
    }
     
    // Return the result
    return count;
}
 
// Driver code
// Given N and X
var N = 7;
var X = 12;
 
// Function Call
document.write( countOccurrences(N, X));
 
</script>
Producción: 

4

 

Complejidad temporal: O(√X)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por mukulbindal170299 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 *