Find the number of cells in the table contains X

0 0 6 minutes read

Given two integer N and X. N represents the number of rows and columns of a table. And the element at the ith row and the jth column in the table is i*j. The task is to find the number of cells in the table that contains X.

Examples:

Input : N = 6, X = 12
Output : 4
Cells {2, 6}, {3, 4}, {4, 3}, {6, 2} contains the number 12

Input : N = 5, X = 11
Output : 0

Approach:
It’s easy to see that number x can appear only once in a row. If x contains in the ith row then the column number will be x/i. x contains in the ith row if x is divisible by i. let’s check that x divides i and x/i <= n. If these conditions met then update the answer.

Below is the implementation of the above approach :

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>

Output

Time Complexity: O(n), since there runs a loop for once from 1 to n.

Auxiliary Space: O(1), since no extra space has been taken.

Approach:

Ignore the cases with negative squares. If n is 0, there won’t be any numbers in the square and if x is 0 it won’t appear in a square, so return 0 in both cases. If x is greater than n^2, it won’t be in the square, so return 0 in that case as well.
Next, loop through all numbers i from 1 to the square root of x, If i is a factor of x and x/i <= n, there are at least two additional places x is on the n-squared chart, due to the associative property: i*(x/i) and (x/i)*i, e.g., if x is 12 and i is 3: 3*4 and 4*3.
Lastly, find out if the square root of x is whole. If it is, it appears one additional time on the diagonal of the n-square table, which is the list of all squares.
| 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 |

Below is the implementation of the above approach :

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>

Output

Time Complexity: O(sqrt(x)), since there runs a loop for once from 1 to n^1/2.

Auxiliary Space: O(1), since no extra space has been taken.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!