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

Question

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

Answer 1

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.