How to convert from decimal to any number system

vector<long long>getRepresentation(long long  n, int base){
	vector<long long>ret;	
	while(n){
		ret.push_back(n%base);
		n/=base;
	}	
	return ret;
}

Bitwise operations

Left-shifting n by k (n << k) multiplies n by 2^k. Right-shifting n by k (n >> k) divides n by 2^k (integer division, remainder dropped).

Classic Binary Search

Search for value x in a sorted array.

int l = 0, r = n - 1;
bool found = false;
while (l <= r) {
    int m = (l + r) / 2;
    if (x == v[m]) { found = true; break; }
    else if (x > v[m]) l = m + 1;
    else r = m - 1;
}

O(log n) per query.

Problems using this

• A. Binary Search

Lower Bound (Closest to the Left)

Find the first index where a[i] >= x (or equivalently, the index where x would be inserted to keep sorted order).

Merge Two Sorted Arrays

Given two sorted arrays a and b, merge them into one sorted array.

Two pointers i and j — always pick the smaller front element:

int i = 0, j = 0, k = 0;
while (i < a.size() || j < b.size()) {
    if (j == b.size() || (i < a.size() && a[i] < b[j])) {
        c[k] = a[i++];
    } else {
        c[k] = b[j++];
    }
    k++;
}

Runs in O(n + m) — optimal since we must look at every element.

Number Theory

Divisors

For example the divisors of a number like 12 (call it n) will be [1, 2, 3, 4, 6, 12].

If we look at them in pairs:

[1, 12]
[2, 6]
[3, 4]

We could just get the first three [1, 2, 3] — call them x — and [4, 6, 12] is y, so x * y = n. By getting x we could get y because we know n.

Prefix Sum & Difference Array

1D Prefix Sum

Given array a[1..n], build a prefix array where pref[i] = a[1] + a[2] + ... + a[i].

Sum of any range [l, r] in O(1):

sum(l, r) = pref[r] - pref[l - 1]

arr[0] = 0;
for (int i = 1; i <= n; i++) {
    arr[i] += arr[i - 1];
}
// query [l, r]:
cout << arr[r] - arr[l - 1];

This works for answering many range-sum queries after O(n) preprocessing.

Basic Frequency Count

Count how many times each value appears in an array:

int freq[n + 1] = {};
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    freq[x]++;
}

freq[v] = how many times v appears.

This is O(n) and works when values are bounded (e.g. 1 ≤ x ≤ n).

Problems using this

• D. Spy Detected! — find the element that appears once (others appear twice)

First Element Appearing K Times

Scan the array while incrementing frequency. Return the first value that reaches frequency k: