0
Challenge · 70Greedy, Bits & Math

The maths you actually need

Techniquesused in ~70% of apps

Not much, and it is always the same few things. Divisors come in pairs so you only ever loop to the square root. Squaring doubles an exponent so big powers take about sixty steps. And when a count gets large you work modulo a prime instead of overflowing.

Core idea. Four facts cover nearly every maths question in a coding round: trial division stops at the square root, a sieve marks multiples instead of testing each number, exponentiation halves the exponent, and greatest common divisor replaces a pair with a smaller one that has the same answer.
Playground, this isn't a screenshot
click a bit position
value90
Each position is worth twice the one to its right. A number is just a set of switches, and the bit operations read and flip them one at a time.

There is nothing mysterious about bit operations. Shift to reach a position, AND to read, OR to set, XOR to flip.

↑ play a little first, then dig in