PROBLEM LINKSDIFFICULTYCakewalk PREREQUISITESloops, simple maths PROBLEMFind number of $(x, y)$ pairs such that $1 \leq x \leq H$, $1 \leq y \leq W$ and $x * y = K$. QUICK EXPLANATIONIterate 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 solutionConstraints 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:
$\mathcal{O}(K log K)$ solutionLet 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?
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)$ solutionLet 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 solutionsIf $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. EDITORIALIST'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 19 Oct '16, 12:42

ans = 0 answered 19 Oct '16, 12:55

MY approach to it in c++:
answered 19 Oct '16, 14:03

import java.util.*; class Chef_and_keyboard { public static void main(String args[]) {
answered 29 Oct '16, 01:16

Hi there. Just wanted to say that in the O(H) solution we have to check if y>=1 and less than width and not height as mentioned in the explanation. answered 29 Mar '17, 12:28

Is O(H) better or O(Klog K) better ... I have used the former. answered 13 Jun '17, 19:16

can some one explain how does the O(sqrt(K)) solution work answered 25 Jun '17, 01:04
