programming cheatsheet
in progress. recursion and dynamic programming to come.
digits
b is the radix/base of the input number n ≥ 0.
number of digits (d)
$$d = \lfloor log_b(n) \rfloor + 1$$
int(log10(1234)) + 1 == 4accessing digits
rightmost digit
$$x = n \bmod{b}$$
1234 % 10 == 4leftmost digit
$$x = \lfloor \frac{n}{b^{d-1}} \rfloor$$
d = 4; int(1234 / 10**(d-1)) == 1nth digit from the left (1-indexed)
$$x = \lfloor \frac{n}{b^{d-N}} \rfloor \bmod{b}$$
N = 3; d = 4; int(1234 / 10**(d-N)) % 10 == 3nth digit from the right (1-indexed)
$$x = \lfloor \frac{n}{b^{N-1}} \rfloor \bmod{b}$$
N = 3; int(1234 / 10**(N-1)) % 10 == 2modifying digits
add y to the nth digit.
from the left (1-indexed)
$$n = n + (y \times b^{d - N})$$
n = 1000; d = 4; y = 2; N = 3; n + y*(10**(d - N)) == 1020from the right (1-indexed)
$$n = n + (y \times b^{N - 1})$$
n = 1000; d = 4; y = 2; N = 3; n + y*(10**(N - 1)) == 1200shifting
shift left
multiply by the base. a bitwise left shift, <<, multiplies by a power of two.
n = 1000; n * 10 == 1000n = 10 (`1010`); n << 1 == 20 (`10100`) == n * 2**1
shift right
divide by the base. a bitwise right shift, >>, divides by a power of two.
reversing a number (base 10)
int reverseNum(int num)
{
int sum = 0;
int remainder = 0;
while(num > 0)
{
remainder = num % 10;
sum = (sum * 10) + remainder;
num = num / 10;
}
return sum;
}
treat the input as a queue: the leftmost digit is the back. take the rightmost digit with modulo 10, then remove it with integer division by 10.
multiply the sum by 10 to shift it left, then append the remainder by adding it. repeat until the input is zero. the sum holds the reversed number.