×

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.

# EDITORIALIST'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 2 ans = 0 Start i from 1 to n    Check if c % i = 0 and c / i <= m       ans++ answered 19 Oct '16, 12:55 593●3●32 accept rate: 8%
 0 MY approach to it in c++: #include #define rep(i,N) for(i=1;i<=N;i++) #define rep1(i,N) for(i=N;i>=1;i--) #define lli long long int using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin>>T; while(T--){ lli n,m,c,count=0,i,j,start; cin>>n>>m>>c; if(n*m
 0 import java.util.*; class Chef_and_keyboard { public static void main(String args[]) {  Scanner sc=new Scanner(System.in); int c[],x[],y[]; System.out.println(); x=new int[sc.nextInt()]; y=new int[x.length]; c=new int[y.length]; for(int i=0;in || i>(c/i)) return count; if(c%i==0) { if(i<=m && (int)c/i<=n && c/i<=m) count+=2; else if(c/i<=m) count++; } } return count; } }  answered 29 Oct '16, 01:16 1 accept rate: 0%
 0 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 2★behram 1●1 accept rate: 0%
 0 Is O(H) better or O(Klog K) better ... I have used the former. answered 13 Jun '17, 19:16 58●5 accept rate: 5%
 0 can some one explain how does the O(sqrt(K)) solution work answered 25 Jun '17, 01:04 43●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×1,688
×281
×98
×63
×45
×2

question asked: 19 Oct '16, 12:42

question was seen: 3,904 times

last updated: 25 Jun '17, 01:04