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