1

I was doing some code challenges and I found this one:

enter image description here

And a guy submitted the following solution:

Int(ceil(log(window / h) / log(bounce))) * 2 - 1

Int means integer

ceil means round up

log means logarithm with base 10

Would you mind explaining this solution please?

Marco Santarossa
  • 113

1 Answers1

2

Let's call the parameter bounce $q$ and $h_k$ the height after $k$-th bounce. Since $h_{k + 1} = q h_k$, it follows that $$h_k = q^kh_0 = q^k h.$$

Let $w$ be the height of the window. If $w \geq h$, the answer is $-1$ (I do not know, why $0$ is inappropriate). Otherwise, the mother sees the ball at least once: when it passes the window after being dropped from the height $h$. After that, it sees it twice for each $k$, for which we have $$h_k > w.$$ (Draw a sketch!) Thus, we are looking for the maximal $k$ for which $$ q^k h > w \Leftrightarrow q^k > w/h$$ still holds.

Can you take it from here?

Antoine
  • 3,439
  • Hi Antoine, thank you for the answer. Can we explain me where hk=q kh0 comes from please? (sorry for silly question) – Marco Santarossa Apr 29 '17 at 19:03
  • $h_0 = h = q^0 h$, $h_1 = q h_0 = q^1 h$, $h_2 = q h_1 = qqh_0 = q^2 h$, etc. You can also prove this by induction: for $k = 0$: beginning of this comment. $k\to k + 1$: $h_{k + 1} = q h_k$ (follows from the formulation of the problem). Induction hypothesis is that $h_k = q^k h$, hence $h_{k + 1} = qq^k h = q^{k + 1}h$. – Antoine Apr 29 '17 at 19:14
  • I apologise for my stupid question. Thank you for your patience and have a good weekend. – Marco Santarossa Apr 29 '17 at 20:18
  • @MarcoSantarossa The question was not stupid, don't worry. – Antoine Apr 29 '17 at 20:40