# count number of appearence of the number k in (n*n) multiplication table

The problem is to count number of appearence of the number k in (n*n) Multiplication table

I just wrote this code to solve this problem

Is there a faster way to solve this problem?

    long n = in.nextLong();
long k = in.nextLong();
long count = 0;
for (long i = 1; i <= n; i++) {
if (k % i == 0 && k / i <= n) {
count++;
}
}
System.out.println(count);


Multiplication table example

thanks <3

• You probably had an idea for an algorithm to code. Which you don't explicitly present in your question, let alone in above code. Did you think about using algebra beyond counting? Is there any symmetry? Oct 23, 2021 at 20:24

I can't say for sure there is no faster way, but there is definitely a cleaner way and also one that is more complete.

• In java it will not slow down your program if you choose more descriptive names.
• I would also extract the function from the logic reading inputs to make it more readable.
• If tableSizes up to 46340 (square root of largest int) are sufficient int will work fine, but even long will only work up until 3,037,000,499. Whichever you use, you might want to throw an error when the inputs exceed these boundaries. I won't in these examples, but it is something to be considered.

For example:

private int multiplicationTableAppearancesFor(int tableSize, int targetNumber) {
int count = 0;
for (int i = 1; i <= tableSize; i++) {
if (targetNumber % i == 0 && targetNumber / i <= tableSize) {
count++;
}
}
return count;
}


Also, your code will run needlessly when the target number is negative ,zero or bigger than tableSize². You could solve this with a check:

private int multiplicationTableAppearancesFor(int tableSize, int targetNumber) {
if (targetNumber < 1 || targetNumber > Math.pow(tableSize, 2)) {
return 0;
}
int count = 0;
for (int i = 1; i <= tableSize; i++) {
if (targetNumber % i == 0 && targetNumber / i <= tableSize) {
count++;
}
}
return count;
}


You could however also include negative tables:

private int multiplicationTableAppearancesFor(int tableSize, int targetNumber) {
if (targetNumber == 0 || targetNumber > Math.pow(tableSize, 2)) {
return 0;
}
int count = 0;
for (int i = 1; i <= Math.abs(tableSize); i++) {
if (targetNumber % i == 0 &&
Math.abs(targetNumber) / i <= Math.abs(tableSize)) {
count++;
}
}
return count * 2; // Times 2 if you want the occurrences in all quadrants
}


To further clean this function you could name the checks for readability, e.g.:

private static boolean divisionOfAbsoluteIsSmallerThan(int dividend, int divisor, int tableSize) {
return Math.abs(targetNumber) / i <= Math.abs(tableSize);
}

private static boolean isDivisibleBy(int dividend, int divisor) {
return targetNumber % i == 0;
}


Altogether that would leave you with this result:

private int multiplicationTableAppearancesFor(int tableSize, int targetNumber) {
if (targetNumber == 0 || targetNumber > Math.pow(tableSize, 2)) {
return 0;
}
int count = 0;
for (int i = 1; i <= Math.abs(tableSize); i++) {
if (isDivisibleBy(targetNumber, i) &&
divisionOfAbsoluteIsSmallerThan(targetNumber, i, tableSize)) {
count++;
}
}
return count * 2; // Times 2 if you want the occurrences in all quadrants
}


There could be a faster way though. You might have noticed that when the targetNumber is smaller than or equal to the table size, it holds true that the occurrences are equal to the number of divisors of the targetNumber. I'm just not sure how to correct for the numbers falling outside of the table, and believe you would end up with similar code and similar complexities. When looking for divisors however, you could possibly get the time complexity down to O(sqrt(n)), because they come in pairs.

• it's fast but still did'n solve it fast as they want and the number can be reach 10^13 anyway thanks for your great effort <3 i'm really grateful <3 Oct 23, 2021 at 20:34
• I think you should be thinking in the direction of getting the divisor pairs for numbers smaller than the target number, up until you reach a number you already have... For example with 12 in a 10x10... 1:12 (12 is too big), 2:6 (+1, and add 6 to a collection), 3:4 (+1, and add 4 to a collection), 4:3 (4 already in collection, break). Then you have all the pairs in the upper triangle and need to double those that aren't NxN... I will happily review your next attempt too. Oct 23, 2021 at 21:12
• You could probably save even more time starting from the target number or size whichever is lower going down... And there might even be some 'magic' algebra I'm missing. People on Mathematics would surely be able to help with that better than I can. Oct 23, 2021 at 21:16