f1nb0.dev / cheatsheet

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 == 4

accessing digits

rightmost digit

$$x = n \bmod{b}$$

1234 % 10 == 4

leftmost digit

$$x = \lfloor \frac{n}{b^{d-1}} \rfloor$$

d = 4; int(1234 / 10**(d-1)) == 1

nth 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 == 3

nth digit from the right (1-indexed)

$$x = \lfloor \frac{n}{b^{N-1}} \rfloor \bmod{b}$$

N = 3; int(1234 / 10**(N-1)) % 10 == 2

modifying 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)) == 1020

from the right (1-indexed)

$$n = n + (y \times b^{N - 1})$$

n = 1000; d = 4; y = 2; N = 3; n + y*(10**(N - 1)) == 1200

shifting

shift left

multiply by the base. a bitwise left shift, <<, multiplies by a power of two.

n = 1000; n * 10 == 1000
n = 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.