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

-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 manera que cada elemento de la array sea igual al producto de sus índices de fila y columna ( 1- indexación basada ).

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: consulte este artículo para conocer el enfoque más simple para resolver el problema al construir la array dada multiplicando los índices de fila y columna para obtener cada elemento de la array y contar el número de ocurrencias de X.

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

Enfoque eficiente: la idea se basa en la observación de que la i ^-ésima fila contiene todos los múltiplos de i en el rango [1, N] . Por lo tanto, X aparece en la i ^-ésima fila si y solo si X es exactamente divisible por i y X/i debe ser menor o igual que N. Si es cierto, incremente el conteo en 1. 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, N] usando la variable i y realizar los siguientes pasos:
  • Si X es divisible por i , almacene el cociente de X / i en una variable, digamos b .
  • Si el valor de b cae en el rango [1, N] , aumente el conteo en 1 .
• 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++ 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)
{
    // Store the required result
    int count = 0;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= n; i++) {
 
        // Check if x is a
        // multiple of i or not
        if (x % i == 0) {
 
            // Check if the other multiple
            // exists in the range or not
            if (x / i <= n)
                count++;
        }
    }
 
    // Print the result
    cout << count;
}
 
// Driver Code
int main()
{
    int N = 7, X = 12;
    countOccurrences(N, X);
 
    return 0;
}

// Java program for the above approach
 
class GFG{
 
// Function to count the occurrences
// of X in the generated square matrix
static void countOccurrences(int n, int x)
{
    // Store the required result
    int count = 0;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= n; i++) {
 
        // Check if x is a
        // multiple of i or not
        if (x % i == 0) {
 
            // Check if the other multiple
            // exists in the range or not
            if (x / i <= n)
                count++;
        }
    }
 
    // Print the result
    System.out.print(count);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7, X = 12;
    countOccurrences(N, X);
 
}
}
 
// This code contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to count the occurrences
# of X in the generated square matrix
def countOccurrences(n, x):
     
    # Store the required result
    count = 0
 
    # Iterate over the range [1, N]
    for i in range(1, n + 1):
 
        # Check if x is a
        # multiple of i or not
        if (x % i == 0):
 
            # Check if the other multiple
            # exists in the range or not
            if (x // i <= n):
                count += 1
 
    # Print the result
    print(count)
 
# Driver Code
if __name__ == "__main__":
     
    N = 7
    X = 12
     
    countOccurrences(N, X)
 
# This code is contributed by ukasp

// C# program for the above approach
using System;
class GFG
{
 
  // Function to count the occurrences
  // of X in the generated square matrix
  static void countOccurrences(int n, int x)
  {
    // Store the required result
    int count = 0;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= n; i++) {
 
      // Check if x is a
      // multiple of i or not
      if (x % i == 0) {
 
        // Check if the other multiple
        // exists in the range or not
        if (x / i <= n)
          count++;
      }
    }
 
    // Print the result
    Console.WriteLine(count);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int N = 7, X = 12;
    countOccurrences(N, X);
  }
}
 
// This code is contributed by splevel62.

<script>
 
// Javascript program for the above approach
 
// Function to count the occurrences
// of X in the generated square matrix
function countOccurrences(n, x)
{
    // Store the required result
    var count = 0;
 
    // Iterate over the range [1, N]
    for (var i = 1; i <= n; i++) {
 
        // Check if x is a
        // multiple of i or not
        if (x % i == 0) {
 
            // Check if the other multiple
            // exists in the range or not
            if (x / i <= n)
                count++;
        }
    }
 
    // Print the result
    document.write( count);
}
 
// Driver Code
var N = 7, X = 12;
countOccurrences(N, X);
 
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(1)