The multiply by $2$ is no different than in elementary school when you're taught how to divide by $10$, $100$, $1000$, etc. by moving the decimal place. Let me do this backwards as an example. Say you are told that the wavelength of green light is $0.000\ 000\ 510$ meters--how many nanometers is this? The conversion is $0.000000510 \text{ meters } * \frac{10^9 \text{ nm}}{1 \text{ meter}}$. So you just multiply by $10^9$ to get the nanometers. This can be done by moving the decimal nine places to the right: first move it three spots: $000.000510$, next move it three more places ($6$ total): $000000.510$, and finally move it three more (total of $9$): $000000510 = 510$ nm.
Converting Fractional Numbers
Finding decimal values for base two is essentially the same. Formally think about what you are trying to do. Let's find the base $2$ form of a value $x$ which we know is positive and less than $1$:
$$
x = n_1 \frac{1}{2} + n_2\frac{1}{2^2} + n_3\frac{1}{2^3} + \dots = \sum_1^\infty a_n \frac{1}{2^n}
$$
Finding the base two representation amounts to finding all $a_n$ (most of which will be $0$ if the number is "nice"--which most aren't). If we multiply both sides by $2$ then what do we get?
$$
2x = n_1 + n_2\frac{1}{2^1} + n_3\frac{1}{2^2} + \dots = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n}
$$
Since this is base $2$, $a_1$ must be either $0$ or $1$. Which one it is will be obvious once we multiply $x$ by $2$. For example if we want to find $x = 0.3125$:
$$
2*0.3125 = 0.625 = a_1 + \sum_1^\infty a_{n+1}\frac{1}{2^n}
$$
$a_1 = 0$ because there is no whole part--we still get a decimal so now we are trying to solve a different problem:
$$
0.625 = \sum_1^\infty b_n\frac{1}{2^n}
$$
This is the same as the original problem! Now we are trying to find the binary representation of $0.625$ (this will give the $b_n$'s). But we need to keep in mind that the $b_n$'s represent $a_{n+1}$ from the original problem! So we recurse:
$$
2*0.625 = 1.25 = b_1 + \sum_1^\infty b_{n+1}\frac{1}{2^n} \rightarrow b_1 = a_2 = 1 \\
0.25 = \sum_1^\infty b_{n+1}\frac{1}{2^n} = \sum_1^\infty c_{n}\frac{1}{2^n} \\
2*0.25 = 0.5 = c_1 + \sum_1^\infty c_{n+1}\frac{1}{2^n} \rightarrow c_1 = b_2 = a_3 = 0 \\
0.5 = \sum_1^\infty c_{n+1}\frac{1}{2^n} = \sum_1^\infty d_{n}\frac{1}{2^n} \\
2*0.5 = 1 = d_1 + \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_1 = c_2 = b_3 = a_4 = 1 \\
0 = \sum_1^\infty d_{n+1}\frac{1}{2^n} \rightarrow d_{n > 1} = c_{n > 2} = b_{n > 3} = a_{n > 4} = 0
$$
So this gives: $0.3125_{10} = 0.0101000\dots_{2}$ or just $0.0101_2$ (which indeed is $0.3125 = \frac{5}{16} = \frac{1}{4} + \frac{1}{16}$).
Converting Integers
Now let's look at converting integers to binary it's essentially the same thing except now you don't have powers of $\frac{1}{2}$, you have powers of $2$:
$$
x = a_0 + a_1*2 + a_2*2^2 + a_3*2^3 + \dots = \sum_0^\infty a_n*2^n = a_0 + \sum_1^\infty a_n*2^n = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n
$$
Hopefully that shows why we should divide by $2$. When we divide by $2$ what we are really doing is writing $x = 2\alpha + \beta$, plug that in:
$$
x = 2\alpha_0 + \beta_0 = a_0 + 2*\sum_0^\infty a_{n + 1}*2^n
$$
Clearly $a_0 = \beta_0$ and $\alpha_0 = \sum_0^\infty a_{n + 1}*2^n$. So again, we recurse:
$$
\alpha_0 = 2\alpha_1 + \beta_1 = a_1 + 2\sum_0^\infty a_{n + 2}*2^n \rightarrow a_1 = \beta_1 \\
\alpha_1 = 2\alpha_2 + \beta_2 = a_2 + 2*\sum_0^\infty a_{n + 3}*2^n \rightarrow a_2 = \beta_2 \\
\dots
$$
So, for instance, we can do $x = 45$:
$$
45 = 2*22 + 1 \rightarrow a_0 = 1\\
22 = 2*11 + 0 \rightarrow a_1 = 0\\
11 = 2*5 + 1 \rightarrow a_2 = 1\\
5 = 2*2 + 1 \rightarrow a_3 = 1\\
2 = 2*1 + 0 \rightarrow a_4 = 0\\
1 = 2*0 + 1 \rightarrow a_5 = 1\\
0 = 2*0 + 0 \rightarrow a_6 = 0 \\
\dots \\
\text{it repeats--these are the zeros to the left of the integer}
$$
So this gives $45_{10} = 0\dots000101101_2$ or just $101101_2$. The way we recursed suggests that we could write:
\begin{align}
45 = & 2*22 + 1 \\
=& 2*\left(2*11 + 0\right) + 1\\
=& 2*\left(2*\left(2*5 + 1\right) + 0\right) + 1\\
=& 2*\left(2*\left(2*\left(2*2 + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*1 + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=& 2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*\left(2*0 + 0\right) + 0\right) + 1\right) + 0\right) + 1\right) + 1\right) + 0\right) + 1 \\
=&\dots
\end{align}
The reason that you divide to get the integer value and multiply to get the fractional value is because you are moving the digits towards the one's place: $2^0$. When the digits are to the left of the decimal (integers) you need to divide by $2$ to move them towards $2^0$ and when the digits are to the right of the decimal (fractions) then you need to multiply by $2$ to bring the digits closer to $2^0$.
Another example: base $3$
Let's say we want to find $45_{10}$ in base $3$. It's the same procedure--divide by $3$:
\begin{align}
45 =& 3*15 + 0 \\
=& 3*\left(3*5 + 0\right) + 0 \\
=& 3*\left(3*\left(3*1 + 2\right) + 0\right) + 0 \\
=& 3*\left(3*\left(3*\left(3*0 + 1\right) + 2\right) + 0\right) + 0 \\
=& 3*\left(3*\left(3*\left(3*\left(3*0 + 0\right) + 1\right) + 2\right) + 0\right) + 0 \\
\end{align}
So now that we are starting to get $0$'s, we know that $45_{10} = 0\dots001200_3 = 1200_3 = 1*3^3 + 2*3^2 = 27 + 18 = 45$
Consider the subproblem of determine if the array has $(i, j)$ such that $0 \le (T[i] + T[j] - k) \le 2$; that is, $k \le T[i] + T[j] \le 2 + k$. Look at the following table for an example algorithm with input $\{a, b, c, d\}$:
$$\begin{array} {c|cccc}
& 0 & 1 & 2 & 3 \\ \hline
0 & a + a & a + b & a + c & a + d \\ \hline
1 & b + a & b + b & a + c & b + d \\ \hline
2 & c + a & c + b & a + c & c + d \\ \hline
3 & d + a & d + b & a + c & d + d \\ \hline
\end{array}$$
If that table were a height map, it would slope up from the bottom left to the top right.
So for any given column, you should be able to find the first row $s$ at least as large as $k$ and the last row $t$ no larger than $2 + k$. If $s \le t$ then you found a solution. If not, find the $s,t$ of the next row. Note that you can use the $s,t$ of the previous row to make the search faster.
Best Answer
This algorithm is essentially counting sort
https://en.m.wikipedia.org/wiki/Counting_sort?fbclid=IwAR1XKmg3EuxUBqJOfTm4HTo8YuOXgP_ZDHy6qIBDR_4cTUqr70DTeT9wiRw
This algorithm can be computed in a single step when there is a diagonal symmetry in the Ferrer diagram
E.g permutations of 5,3,2,1,1
Or permutations of 4,3,2,1