Math, geometry and bit-trick ladder: six coding-round techniques, step by step

In this article

1. Before you start
2. Why interviewers ask this
3. The math, geometry and bit tricks ladder from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one rung of the coding interview patterns and method path.

Why interviewers ask this

Candidates report questions from this family in coding rounds at large tech companies: find the most points on one line, decide whether two rectangles overlap, count pairs whose sum is divisible by k, raise a number to a power, or write sine from its series. None of them needs advanced mathematics. Each one tests whether you reach for an exact integer method and then name the input that breaks the obvious one.

A weak answer uses a floating-point slope, a loop that multiplies one hundred thousand times, or a check that fails on zero. A strong answer states the assumption (does touching count? can points repeat?), writes the integer version and tests the boundary. A Staff-level answer also gives the cost and says what changes if the numbers get large. Everything below follows that pattern, one rung at a time.

The math, geometry and bit tricks ladder from first principles

Bit trick

A bit trick is a short expression that uses bitwise operators on the binary digits of an integer to answer a question about those digits, such as "is exactly one digit set?" or "how many digits are set?", in a handful of operations instead of a loop over every digit.

Binary exponentiation

Binary exponentiation is a method that computes a power by reading the exponent in binary and squaring the base once per binary digit, so the number of multiplications grows with the digit count of the exponent rather than with the exponent itself.

Cross product test

The cross product test is a single integer computed from the coordinates of three points that is positive, negative or zero according to whether the third point lies left of, right of or exactly on the line through the first two, with no division and no floating point.

Taylor series

A Taylor series is a sum of terms built from a function's derivatives at one point that, added far enough, approximates the function near that point; for sine it is x minus x cubed over 3 factorial, plus x to the fifth over 5 factorial, and so on.

In plain words

Think of a ladder where each rung is a way to avoid doing work. Instead of checking every binary digit, you flip one. Instead of multiplying a number a million times, you square it twenty times. The analogy breaks here: a ladder only goes up, while these rungs also share ideas. Remainders and the greatest common divisor (gcd) reappear in the geometry rung.

In one precise sentence, every rung swaps a slow or fragile calculation for an exact or error-bounded one, and states the single input that still breaks it.

Step 1: Bit masks test and count bits in one line

The expression n & (n - 1) clears the lowest set bit of n, so a number is a power of two exactly when the result is zero and n is positive. The Stanford bit-twiddling collection lists both the power-of-two test and Brian Kernighan's way of counting set bits as separate entries.

Run the clearing step on 12, binary 1100: it leaves 1000, then 0, so the loop runs twice and 12 has two set bits.¹ For 16 it runs once.¹ For 0 it never runs, and the bare test (n & (n - 1)) == 0 answers "yes, a power of two", which is wrong; the safe test adds n > 0.¹ You now have the rung: one operation, one named failure. The number of set bits is also the core of Hamming distance, and bit positions are a different question from byte order.

Step 2: Binary exponentiation computes a power in a few squarings

To compute a power, read the exponent in binary. For 2 to the 10th, the exponent is 1010. Square the base at each digit and multiply it into the result only where the digit is one. That takes 3 squarings and 2 multiplications, 5 in all, against 9 for the plain loop.¹ The cp-algorithms page on binary exponentiation gives the recursive and iterative forms of this method.

def power(base, exp):
    result = 1
    while exp:
        if exp & 1:        # this binary digit of the exponent is one
            result *= base
        exp >>= 1
        if exp:
            base *= base   # square for the next digit
    return result

The same method written recursively takes four lines:

def power_rec(base, exp):
    if exp == 0: return 1
    half = power_rec(base, exp // 2)
    return half * half * (base if exp & 1 else 1)

The recursion goes as deep as the exponent has binary digits. For a negative exponent, compute the power of the reciprocal 1 / base, which is a fraction, or state that integer exponents must be non-negative.

The cost is at most about twice the digit count of the exponent. For an exponent of one million that is at most 40 multiplications against 999,999 for the plain loop.¹ Input: base and exponent. Output: the power. Reducing every product by a remainder gives modular exponentiation with the same loop.

Step 3: Remainder counting finds pairs with a divisible sum

To count pairs in a list whose sum is divisible by k, group the numbers by their remainder after dividing by k. A pair works when the two remainders add to k, or are both zero. Scan the list once; for each number, look up how many earlier numbers have the remainder that completes it, then record this number's remainder.

For the illustrative list 3, 6, 1, 4, 2, 5, 9 with k = 3, the remainder counts are three zeros, two ones and two twos, and the count is 3 + 2 × 2 = 7, which matches a brute-force check of every pair.¹ The cost is linear in the list length instead of quadratic. The same remainder idea powers subarray sum equals k.

One trap lives here. In Java and C, a negative number's % result can be negative, because the remainder takes the sign of the dividend (Java Language Specification §15.17.3; C99 §6.5.5). For minus 7 and 3, Python gives 2 and a truncating remainder gives minus 1.¹ A negative remainder is fixed by adding the modulus before the final remainder: ((x % k) + k) % k. Python's own rule already gives the first value. See Python interview questions for related language details.

Step 4: Rectangle bounds decide overlap and the shared region

Two axis-aligned rectangles overlap when their ranges overlap on both axes. Give each as left, bottom, right, top. The shared region has left equal to the larger of the two lefts, right equal to the smaller of the two rights, and the same for bottom and top. If that left is greater than that right, or that bottom is greater than that top, there is no overlap. This is the two-dimensional version of merging intervals.

Take A as (0, 0, 4, 3) and B as (2, 1, 6, 5): the shared region is (2, 1, 4, 3), area 4.¹ Take C as (4, 0, 6, 3): the region has zero width, a segment on the shared edge.¹ A rectangle D at (5, 4, 7, 6) gives no region at all.¹

The decision to make out loud is whether touching counts. The bank wording "return all the points of intersection" also has two readings, so ask which one is meant. Reading one is the corners of the overlap region: for A and B those are (2, 1), (4, 1), (2, 3) and (4, 3). For a segment it is the segment's ends, and for a corner touch it is one point.

Reading two is the points where the two boundaries cross: for A and B only (4, 1) and (2, 3), because B's bottom edge meets A's right edge, and B's left edge meets A's top edge.¹ The corners (2, 1) and (4, 3) belong to the region but are not crossings, since each is a corner of one rectangle lying inside the other.

Step 5: Reduced directions and cross products find the best line

To find the most points on one line, fix each point as an anchor. For every other point take the difference in x and y, divide both by their greatest common divisor, and fix the sign. The greatest common divisor is the largest whole number that divides both numbers. The resulting pair of integers names the direction exactly, so a hash map can count it. The best count plus one for the anchor is the answer through that anchor.

For the points (1,1), (2,2), (3,3), (3,1), anchor (1,1) sees direction 1/1 twice, so the best line holds 3 points.¹ The cost is quadratic in the number of points. The cross product test is the alternative: three points are collinear exactly when (bx-ax)*(cy-ay) - (by-ay)*(cx-ax) is zero.

Slopes as doubles are risky: for the points (0, 0), (1000000000, 1000000001) and (1000000001, 1000000002), which are not collinear, both slopes round to the same double, 1.000000001, so a slope comparison calls the triple collinear, while the integer cross product is exactly minus 1.¹ A point equal to the anchor needs care too: gcd(0, 0) is 0, and dividing by it fails, so skip duplicates before reducing and count them separately.¹ The same exact arithmetic helps with closest-point questions, where comparing squared distances avoids square roots.

Step 6: A Taylor series builds sine from additions and multiplications

To implement sine, add the terms x, minus x cubed over 3 factorial, plus x to the fifth over 5 factorial, and so on, each term built from the last one. Computing each term by multiplying the previous one by x squared and dividing by two numbers avoids huge factorials.

For x = 1 the true sine is 0.8414709848; one term leaves an error of 0.1585, three leave 0.0001957, and five leave 2.489e-08.¹ The series works well only near zero. For x = 10, five terms give about 1448.272 instead of the true value of minus 0.544021, while reducing the argument first to minus 2.566371 (by subtracting a multiple of two pi) gives minus 0.544785, within 0.0007642.¹ A strong answer therefore does two things: reduce the argument, and stop when the next term falls below a stated tolerance.

1 · Bit masks2 · Fast power3 · Remainder counts4 · Rectangle bounds5 · Lines6 · SeriesReplay

Step-by-step description

1. n & (n - 1) clears the lowest set bit.
2. Square once per binary digit of the exponent.
3. Group numbers by remainder, scan once.
4. Larger lefts and smaller rights give the shared region.
5. Reduced directions or cross products stay exact.
6. Reduce the argument, stop at a tolerance.

• A power of two needs the number to be positive and the bit mask to clear to zero.
• Binary exponentiation squares once per exponent digit.
• Each rung swaps a slow or fragile calculation for an exact or error-bounded one.

Worked example

The six traces above come from one saved script, so every value can be checked with a calculator.¹ The table collects the values that decide the answers.

The series accuracy follows a clear pattern: one term gives 0.8 correct decimal places, two give 2.1, three give 3.7, four give 5.6 and five give 7.6.¹

Text description of the diagram

• One term gives 0.8 correct decimal places.
• Five terms give 7.6 correct decimal places.
• Each extra Taylor term adds roughly two correct decimal places.

Trade-offs and edge cases

Every quick check on the ladder has one input that breaks it, and the table lists them.

Text description of the diagram

• The bare power-of-two test accepts zero, so the safe version adds a positive check.
• Slopes as doubles are replaced by reduced integer pairs.
• A negative remainder is fixed by adding the modulus before the final remainder.

Beyond the table, three cases decide real answers. First, overflow: the cross product multiplies two coordinate differences, so with large coordinates use a wider integer type (a 64-bit long in Java) or Python's unbounded integers. Second, duplicate points: in the line problem, skip a point equal to the anchor before reducing, because gcd(0, 0) is 0 and dividing by it fails; count each repeat separately and add it to every direction. Third, cost: reduced-direction counting is quadratic in time with linear extra memory, which is fine for a few thousand points; the cross-product version fixes each pair and tests every third point, so it is cubic, and it suits only small inputs or a single collinearity check.

For power, large exponents with a remainder need the modular form, because the plain result can overflow long before the exponent is large. For series, a polynomial approximation that is good near zero is bad far away, which is why library routines reduce the argument first. Whenever two readings of the question are possible, say your assumption aloud before you code.

How to answer it in an interview

The spoken structure: name the exact representation first, then the loop, then the cost, then the one input that breaks it.

Common mistakes

• "A number is a power of two when n & (n - 1) is zero." (wrong) Zero passes. (right) "It is a power of two when n is positive and n & (n - 1) is zero."
• "I compare slopes as doubles." (wrong) Nearly collinear points can look equal or different by rounding. (right) "I compare reduced integer pairs, or the integer cross product."
• "The rectangles overlap if their edges are not apart." (wrong) That silently counts touching. (right) "I'll treat touching as overlap or not, depending on what you want, and say so."
• "I'll write the test as n & (n - 1) == 0." (wrong) In C and Java, == binds tighter than &, so it parses as n & ((n - 1) == 0): a bug in C, a compile error in Java. (right) "I parenthesise it: (n & (n - 1)) == 0." In Python the bare form happens to parse as intended, but the habit travels badly.
• "I'll compute the power with a loop, since the exponent is small." (wrong) The exponent may not stay small. (right) "I'll square per binary digit, which is logarithmic in the exponent."

Follow-up questions

Given two dates (DDMMYY), find whether they are 1-month apart?

First decide what "one month apart" means: the same day number in the next month, or a fixed number of days. Then parse each date into day, month and year, choose a rule for the two-digit year, and handle the case where the later month is shorter than the day number.

Given this collision diagram, which object is bigger and which way does the merged mass move?

Assuming the objects stick together along one line, momentum (mass times velocity) is conserved, so the merged velocity is total momentum divided by total mass. For the illustrative masses 3 and 1 at velocities 2 and minus 4, total momentum is 2 and the merged velocity is 0.5, so the merged mass moves in the positive direction.¹

With the masses 3 and 1 given, the first object (mass 3) is the bigger one. Separately, its momentum of 6 against minus 4 for the second sets the direction, so the merged mass moves the first object's way.¹ If only a diagram of velocities is given, the merged velocity's direction shows which momentum is larger, not which mass is larger. State the sticking assumption, because an elastic bounce uses different formulas.

How many Taylor terms are enough when you implement sin(x)?

Stop when the absolute value of the next term is below your stated tolerance, after reducing the argument to a small range. For x = 1, five terms leave an error of 2.489e-08.¹

How do you count set bits for many numbers quickly?

If you count one number, Brian Kernighan's loop runs once per set bit. For many numbers, precompute counts for small groups of bits in a lookup table; the Stanford collection lists table and parallel methods as well.

Can fast exponentiation work with a remainder?

Yes: reduce each product by the modulus inside the same loop, so values never grow past the square of the modulus. The loop is otherwise unchanged, and the same remainder idea underlies counting pairs and prefix sums.

Sources

1. Bit Twiddling Hacks (Sean Eron Anderson, Stanford Graphics) — Stanford Computer Graphics Laboratory (page undated; accessed 2026-10-26), 26 Oct 2026
2. Binary Exponentiation — cp-algorithms (page undated; accessed 2026-10-26), 26 Oct 2026
3. The Java Language Specification, SE 21: Remainder Operator % — Oracle (accessed 2026-10-26), 26 Oct 2026
4. The Python Language Reference: Binary arithmetic operations — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026