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 12Input : 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 Xint 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 codeint 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 Xdef 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 codeif __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 Xfunction 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> |
4
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 Xint 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 codeint 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 Xclass 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 Xdef 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 Coden = 6x = 12print(Cells(n, x))# This code is contributed by rag2127. |
C#
// C# program to find number of// cells in the table contains Xusing System;class GFG{// Function to find number of// cells in the table contains Xpublic 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 codestatic 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 Xfunction 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 Codevar n = 6, x = 12;// Function calldocument.write(Cells(n, x));// This code is contributed by Khushboogoyal499</script> |
4
Time Complexity: O(sqrt(x)), since there runs a loop for once from 1 to n1/2.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
