# Probability interview question

Suppose we have three positive integers $A, B, C$. We randomly choose an integer $a$ in the range $[0,A]$ and an integer $b$ in the range $[0,B]$. Find the probability that $a + b\leq C$.

I am unable to proceed in this question. Any hints .

• Well, what's C? – Newb Oct 3 '14 at 9:14
• The source where I read the question nothing has been given about C. It's just a positive integer – abkds Oct 3 '14 at 9:15
• We will have to take all possible cases – abkds Oct 3 '14 at 9:15

Assuming that each integer in given range has the same probability to be choosen, you have to count the cases when the inequality holds and divide it by all cases, namely: $$\frac{\sum_{a=0}^A\sum_{b=0}^B\mathbf{1}(a+b\leq C)}{(A+1)\cdot (B+1)}$$ where $\mathbf{1}(P)=1$ if proposition $P$ is true and $\mathbf{1}(P)=0$ otherwise.

• Shouldn't denominator be $(A+1).(B+1)$ ? Because zero is also included in the interval – abkds Oct 3 '14 at 9:20
• @AbhishekKDas Yes, and $a$ and $b$ should both start at $0$. However, the idea is correct, which of course is the main thing. – drhab Oct 3 '14 at 9:28
• If A and B are large (say around a million) you would obviously not count the numbers, but calculate them. At least you would for each a, 0 ≤ a ≤ A, calculate how many values 0 ≤ b ≤ B there are such that a + b ≤ C; that number would be min (B + 1, max (C - A + 1, 0)). – gnasher729 Oct 3 '14 at 10:08

Let $S_C$ be the number of couples $(a,b)$, $a\in [0,A]$ and $b\in [0,B]$ such that $a+b \leq C$. It is clear that $S_0=1$ because the only couple that can sum up to zero is $(0,0)$. Moreover if $C>A+B$ then $S_C=S_{A+B}$ since all couples that are counted in $S_C$ were already counted in $S_{A+B}$. Without loss in generality we can assume that $A\leq B$. Let us study the function $T_C=S_{C+1}-S_C$. It corresponds to the number of couples $a,b$ where $a+b=C$. This is easier to count , e.g. if A and B are big enough then for $T_3$ we count the couples $(3,0), (2,1), (1,2)$ and $(0,3)$. In fact we can conclude easily then for $C$ small enough we have $T_C=C+1$. But this only works if $C \leq A$. Once $C>A$ we must start off with $(A,C-A),(A-1,C-A+1),\ldots,(0,C)$ (on the condition that $B$ is big enough so that $C-A \in [0,B]$). In this case we will have $T_C=A+1$. But this can not continue forever since in case $C>B$ we will not even arrive to $(0,C)$ but only to $(C-B,B)$. We conclude that for $C>B$ we have $T_C=A+B-C+1$ so globally we have :$$T_C = \begin{cases} C+1, & \text{for C \leq A} \\ A+1, & \text{for A \leq C \leq B}\\ A+B-C+1, & \text{for B \leq C \leq A+B+1 }\\ 0, & \text{for A+B+1 \leq C }\\ \end{cases}$$ To reconstruct $S$ all we have to do is to "integrate" this function over the different domains. A bit of calculation gives: $$S_C = \begin{cases} C(C+1)/2, & \text{for C \leq A} \\ A(A+1)/2+(A+1)(C-A), & \text{for A \leq C \leq B}\\ f(C), & \text{for B \leq C \leq A+B+1 }\\ (A+1)(B+1) & \text{for A+B+1 \leq C }\\ \end{cases}$$ Where $f(C)=(A+1)(B+1)-(A+B+1-C)(A+B+1-C+1)/2$.

If $a$ and $b$ are independent there is a very simple solution. First convince yourself that $$a + b \leq C \Leftrightarrow \mathrm{max}(a,b) \leq \frac{C}{2}$$

Then due to independence, $P\{\mathrm{max}(a,b) \leq \frac{C}{2}\} = P\{a \leq \frac{C}{2}\}P\{b \leq \frac{C}{2}\}$

I am assuming both $a$ and $b$ have uniform distributions. Then, $P\{a \leq \frac{C}{2}\} = \frac{\lfloor\frac{C}{2}\rfloor+1}{A+1}$. Likewise, $P\{b \leq \frac{C}{2}\} = \frac{\lfloor\frac{C}{2}\rfloor+1}{B+1}$. Therefore,

$$P\{a + b \leq C\} = \frac{\left(\lfloor\frac{C}{2}\rfloor+1\right)^2}{(A+1)(B+1)}$$

I made the implicit assumption that $A$ and $B$ are larger than $\frac{C}{2}$. But I guess it is clear how you would adapt the solution for the cases not covered by this assumption.

Can be done in $\min(O(A\log B),O(B\log A))$ using binary serach.