Basic Problem Solving Tips

--i when erase() element inside loop

if erase() an element inside a for or while loop, we must do --i i.e. decrease i to the prevous index as the size() of container became 1 less.

for (int i = 0; i < v.size() - 1; i++) {
  v.erase(v.begin() + (i + 1));
  --i;
}

gcd tricks

use __gcd(a, b) or gcd(a, b) from <numeric> C++ STL

caution

• gcd(a, b) == 1 when a and b are consecutive numbers ie. b = a+1 or a = b+1

---

• for n is ODD, x is ODD, gcd(a, b) == 2

  • gcd(n - x, n + x) == 2 when a and b are equally separated = ODD x from the middle element n; gcd is 2

• for n is ODD, x is EVEN, gcd(a, b) == 1

  • gcd(n - x, n + x) == 1 when a and b are equally separated = EVEN x from the middle element n; gcd is 1

---

• for n is EVEN, x is ODD, gcd(a, b) == 1

  • gcd(n - x, n + x) == 1 when a and b are equally separated = ODD x from the middle element n; gcd is 1

• for n is EVEN, x is EVEN, gcd(a, b) == 2

  • gcd(n - x, n + x) == 2 when a and b are equally separated = EVEN x from the middle element n; gcd is 2

• gcd(a, a) == a

lcm tricks

use lcm(a, b) from <numeric> C++ STL

• lcm(a, a) == a

gcd and LCM relation

info

[ lcm(a, b) * gcd(a, b) ] = [ a * b ]
⏬
lcm(a, b) = [ (a*b)/(gcd(a, b)) ]

![gcd_lcm_relation](/img/docs-images/greatest_common_divisor.svg)