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