Encuentre el número de celdas en la tabla que contiene X

Posted on by Rudeus Greyrat

Dados dos enteros N y X . N representa el número de filas y columnas de una tabla. Y el elemento en la i-ésima fila y la j-ésima columna de la tabla es i*j . La tarea es encontrar el número de celdas en la tabla que contiene X . 

Ejemplos: 

Entrada: N = 6, X = 12 
Salida: 4 
celdas {2, 6}, {3, 4}, {4, 3}, {6, 2} contiene el número 12 

Entrada: N = 5, X = 11 
Salida: 0 

Enfoque: 
es fácil ver que el número x puede aparecer solo una vez en una fila. Si x contiene en la i-ésima fila, entonces el número de columna será x/i . x contiene en la i-ésima fila si x es divisible por i . comprobemos que x divide i y x/i <= n . Si se cumplen estas condiciones, actualice la respuesta.

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

C++

// CPP program to find number of
// cells in the table contains X
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of
// cells in the table contains X
int Cells(int n, int x)
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (x % i == 0 && x / i <= n)
            ans++;
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 6, x = 12;
 
    // Function call
    cout << Cells(n, x);
 
    return 0;
}

Java

// Java program to find number of
// cells in the table contains X
class GFG
{
 
    // Function to find number of
    // cells in the table contains X
    public static int Cells(int n, int x)
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (x % i == 0 && x / i <= n)
                ans++;
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 6, x = 12;
 
        // Function call
        System.out.println(Cells(n, x));
    }
}
 
// This code is contributed by sanjeev2552

Python3

# Python3 program to find number of
# cells in the table contains X
 
# Function to find number of
# cells in the table contains X
def Cells(n, x):
 
    ans = 0;
    for i in range(1, n + 1):
        if (x % i == 0 and x / i <= n):
            ans += 1;
 
    return ans;
 
# Driver code
if __name__ == '__main__':
 
    n = 6; x = 12;
 
    # Function call
    print(Cells(n, x));
 
# This code is contributed by 29AjayKumar

C#

// C# program to find number of
// cells in the table contains X
using System;
 
class GFG
{
    // Function to find number of
    // cells in the table contains X
    static int Cells(int n, int x)
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (x % i == 0 && x / i <= n)
                ans++;
 
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 6, x = 12;
         
        // Function call
        Console.WriteLine(Cells(n,x));
    }
}
 
// This code is contributed by nidhiva

Javascript

<script>
 
// JavaScript program to find number of
// cells in the table contains X
 
// Function to find number of
// cells in the table contains X
function Cells(n, x)
{
    let ans = 0;
    for (let i = 1; i <= n; i++)
        if (x % i == 0 && parseInt(x / i) <= n)
            ans++;
 
    return ans;
}
 
// Driver code
    let n = 6, x = 12;
 
    // Function call
    document.write(Cells(n, x));
 
</script>
Producción

4

Complejidad Temporal: O(n), ya que corre un bucle por una vez de 1 a n.

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

Enfoque :

 Ignore los casos con cuadrados negativos. Si n es 0, no habrá ningún número en el cuadrado y si x es 0, no aparecerá en un cuadrado, por lo que devuelve 0 en ambos casos. Si x es mayor que n^2, no estará en el cuadrado, así que devuelva 0 en ese caso también. 
A continuación, recorra todos los números i desde 1 hasta la raíz cuadrada de x . Si i es un factor de x y x/i <= n , hay al menos dos lugares adicionales en los que x está en el gráfico de n cuadrados, debido a la propiedad asociativa: i*(x/i) y (x/i)*i , por ejemplo, si x es 12 e i es 3: 3*4 y 4*3. 
Por último, averigua si la raíz cuadrada de x es entera. Si es así, aparece una vez más en la diagonal de la tabla de n cuadrados, que es la lista de todos los cuadrados.
| 1 | 2 | 3 | 4 | 5 | 6 |

| 2 | 4 | 6 | 8 | 10 | 12 |

| 3 | 6 | 9 | 12 | 15 | 18 |

| 4 | 8 | 12 | 16 | 20 | 24 |

| 5 | 10 | 15 | 20 | 25 | 30 |

| 6 | 12 | 18 | 24 | 30 | 36 |

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

C++

// C++ program to find number of
// cells in the table contains X
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of
// cells in the table contains X
int Cells(int n, int x)
{
    if (n <= 0 || x <= 0 || x > n * n)
        return 0;
         
    int i = 0, count = 0;
    while (++i * i < x)
        if (x % i == 0 && x <= n * i)
            count += 2;
             
    return i * i == x ? count + 1 : count;
}
 
// Driver code
int main()
{
    int n = 6, x = 12;
 
    // Function call
    cout << (Cells(n, x));
    return 0;
}
 
// This code is contributed by subhammahato348

Java

// Java program to find number of
// cells in the table contains X
class GFG {
 
    // Function to find number of
    // cells in the table contains X
    public static int Cells(int n, int x)
    {
        if (n <= 0 || x <= 0 || x > n * n)
            return 0;
        int i = 0, count = 0;
        while (++i * i < x)
            if (x % i == 0 && x <= n * i)
                count += 2;
        return i * i == x ? count + 1 : count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 6, x = 12;
 
        // Function call
        System.out.println(Cells(n, x));
    }
}
 
// This code is contributed by stephenbrasel

Python3

# Python program to find number of
# cells in the table contains X
  
# Function to find number of
# cells in the table contains X
def Cells(n, x):
    if (n <= 0 or x <= 0 or x > n * n):
        return 0;
    i = 1
    count = 0
     
    while (i * i < x):
        if (x % i == 0 and x <= n * i):
            count += 2;
        i+=1
     
    if(i * i == x):
        return count + 1
    else:
        return count
 
# Driver Code
n = 6
 
x = 12
 
print(Cells(n, x))
 
# This code is contributed by rag2127.

C#

// C# program to find number of
// cells in the table contains X
using System;
 
class GFG{
 
// Function to find number of
// cells in the table contains X
public static int Cells(int n, int x)
{
    if (n <= 0 || x <= 0 || x > n * n)
        return 0;
         
    int i = 0, count = 0;
    while (++i * i < x)
        if (x % i == 0 && x <= n * i)
            count += 2;
             
    return i * i == x ? count + 1 : count;
}
 
// Driver code
static public void Main ()
{
    int n = 6, x = 12;
 
    // Function call
    Console.WriteLine(Cells(n, x));
}
}
 
// This code is contributed by kirti

Javascript

<script>
 
// JavaScript program to find number of
// cells in the table contains X
 
// Function to find number of
// cells in the table contains X
function Cells(n, x)
{
    if (n <= 0 || x <= 0 || x > n * n)
        return 0;
         
    var i = 0, count = 0;
     
    while (++i * i < x)
        if (x % i == 0 && x <= n * i)
            count += 2;
             
    return i * i == x ? count + 1 : count;
}
 
// Driver Code
var n = 6, x = 12;
 
// Function call
document.write(Cells(n, x));
 
// This code is contributed by Khushboogoyal499
 
</script>
Producción

4

Complejidad de tiempo: O (sqrt (x)), ya que se ejecuta un bucle por una vez de 1 a n 1/2 .

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

Publicación traducida automáticamente

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