CHEFKEY - Editorial

editorial
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Cakewalk

PREREQUISITES

loops, simple maths

PROBLEM

Find number of (x, y) pairs such that 1 \leq x \leq H, 1 \leq y \leq W and x * y = K.

QUICK EXPLANATION

Iterate over x and you can check if there exists a valid y in the desired range satisfying x \cdot y = K or not.

EXPLANATION

##\mathcal{O}(H * W) bruteforce solution

Constraints on H and W are quite small. We can exploit these to get a
simple bruteforce solution. We iterate over all (x, y) pairs and check
whether their product x * y is equal to K or not. We can count such
valid pairs in \mathcal{O}(W * H) time.

Pseudo Code:

ans = 0
for x = 1 to H:
  for y = 1 to W:
    if x * y == K:
      ans++

##\mathcal{O}(K log K) solution
Let us make a simple change in the last solution? What if we you stop iterating over y when the value
of x * y exceeds K. Will that improve time complexity?

ans = 0
for x = 1 to H:
  for y = 1 to W:
    if x * y > K:
      break;
    if x * y == K:
      ans++

Yes, it will. Let us estimate it. From a casual look, it looks that
its time complexity will still be \mathcal{O}(H * W). But it’s not. Let us
delve into depth.

For each x, the inner loop over y will run at most \frac{K}{x} times. So,
total number of iterations the program will be run will be given by

\frac{K}{1} + \frac{K}{2} + \dots + \frac{K}{H}
\leq \frac{K}{1} + \frac{K}{2} + \dots + \frac{K}{K}
\leq K \cdot (\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{K})

The expression

\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n}

is also known as harmonic sum H_n. One can prove that H_n = \mathcal{O}(log \, n).

Hence, the time complexity will be \mathcal{O}(K log K).

##\mathcal{O}(H) solution
Let us exploit the condition x * y = K. For a fixed x, do we really need to iterate
over all y's to check how many of them satisfy x * y = K. It turns out, no. Firstly there will be at most a single y. If K is not divisible by x, then there can’t exist such y. Otherwise y will be \frac{K}{x}.

In summary, we iterate over only
x values and find the corresponding y (if it exists), and
check whether the y is \geq 1 and \leq H.

Time complexity of this method will be \mathcal{O}(H), as are iterating over x values only once.

Factorization based solutions

If x \cdot y = K, then both x and y should divide K. So we can find all the divisors of the K. Let x be one such divisor, then y will be \frac{K}{x}.

You can find all the divisors of K in \mathcal{O}(sqrt(K)) time.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.