Problem

Given integers N and X, write a function that returns the number of times X appears as a value in an N by N multiplication table.

Suppose you have a multiplication table that is N by N. That is, a 2D array where the value at the i-th row and j-th column is (i + 1) * (j + 1) (if 0-indexed) or i * j (if 1-indexed).

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: n = 6, x = 12
Output: 4
Explanation: 
This is how multiplication table will look like:
|  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 |

And all the 12’s are highlighted below:

$$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 6 & 8 & 10 & \color{orange} 12 \\ 3 & 6 & 9 & \color{orange} 12 & 15 & 18 \\ 4 & 8 & \color{orange} 12 & 16 & 20 & 24 \\ 5 & 10 & 15 & 20 & 25 & 30 \\ 6 & \color{orange} 12 & 18 & 24 & 30 & 36 \end{bmatrix} $$

Solution

Method 1 -Simple Iteration with division operator

We can iterate from 1 to N for both row (i) and column (j) indices and count each time their product equals X.

We can see that for number x to occur, we need i * j == x. That means x is divisibly by both i and j. x % i == 0 and x % j == 0.

But for eg. x = 12, we can choose i = 6, j = 2, then it is good. x % i == 0 and x % j == 0. We cannot choose, i = 1, j = 12, even though x % i == 0 and x % j == 0 still holds, but it will not exist in table. So:

  • If X is divisible by i and the division result is <= N, then this pair (i, j) is a valid occurrence in the table.

Also, to optimize, you can iterate only one index (either row or column), and for each value i, you can calculate whether a corresponding j exists such that i * j == x.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public class Solution {

	public int findInMultiplicationTable(int N, int X) {
		int count = 0;

		for (int i = 1; i <= N; i++) {
			if (X % i == 0 && X / i  <= N) {
				count++;
			}
		}

		return count;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Iterate till square root of n

Lets look at the square table again. The idea is that if you have a multiplication of two integers i and j that equals X (where i and j are within the range [1, N]), then one of the integers must be less than or equal to sqrt(X), and the other must be greater than or equal to sqrt(X) and less than or equal to N. $$ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 6 & 8 & 10 & \color{orange} 12 \\ 3 & 6 & 9 & \color{orange} 12 & 15 & 18 \\ 4 & 8 & \color{orange} 12 & 16 & 20 & 24 \\ 5 & 10 & 15 & 20 & 25 & 30 \\ 6 & \color{orange} 12 & 18 & 24 & 30 & 36 \end{bmatrix} $$

Look at the diagonal elements, they are perfect squares - 1, 4, 9, 16… if that is the case, we should add 1 more to the answer, as this value occurs on diagonal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {

	public int findMultiplicationOccurrences(int N, int X) {
		int count = 0;
		// Start from 1 to the square root of X since i * j = X implies i ≤ sqrt(X) or j ≤ sqrt(X). 
		for (int i = 1; i <= Math.min(N, Math.sqrt(X)); i++) {
			// Check if X is divisible by i to find the corresponding j
			if (X % i == 0) {
				int j = X / i;
				// Check if j is within the bounds of the multiplication table
				if (j <= N) {
					count++;
					// If i and j are distinct, count this as an additional occurrence
					if (i != j && j  < = Math.sqrt(X)) {
						count++;
					}
				}
			}
		}

		return count;
	}

}

Complexity

  • ⏰ Time complexity: O(√x)
  • 🧺 Space complexity: O(1)