Calculate square of a number without using multiplication, division and pow()

The problem, simply

You get a whole number n. Give back n * n, the square of n.

The catch: you may not use the times sign *, the divide sign /, or Math.pow. You may add, subtract and use the bit tools, like shifting bits left and right. The number can be negative, and a square is never negative.

A story to remember it

Picture it

Examples

Way 1: the simple way

Times is only adding again and again. 5 times 5 is 5 + 5 + 5 + 5 + 5.

1. Make n positive, because the square of -n is the same as the square of n.
2. Start a total at 0.
3. Add n to the total, n times.

class Solution {
    public static long square(int n) {
        long num = Math.abs((long) n);   // make it positive, in a long so it cannot overflow
        long total = 0;
        for (long i = 0; i < num; i++) {
            total += num;                // add n, n times
        }
        return total;
    }
}

How long it takes: the loop runs n times, O(n). For n near 46,000 that is 46,000 adds for one answer. Extra room: one total, O(1).

Way 2: the clever way

Look at the bits of n. Every bit that is on stands for a power of two inside n. Shifting a number left by i places is the same as doubling it i times. So we keep a pile that doubles each round, and add the pile to the total only when the matching bit of n is on.

1. Make n positive. Let pile = n and total = 0.
2. While n still has bits: if the lowest bit is 1, add pile to total.
3. Double the pile with pile << 1. Drop the lowest bit of n with n >> 1.
4. When n reaches 0, total is the square.

class Solution {
    public static long square(int n) {
        long bits = Math.abs((long) n);  // whose bits we read
        long pile = bits;                // n times 1, then n times 2, 4, 8, ...
        long total = 0;
        while (bits > 0) {
            if ((bits & 1) == 1) {
                total += pile;           // this power of two is inside n
            }
            pile <<= 1;                  // double the pile
            bits >>= 1;                  // look at the next bit
        }
        return total;
    }
}

How long it takes: one round per bit of n, and n has about log n bits, O(log n). For any int that is at most 31 rounds. Extra room: three numbers, O(1).

Another way: cut it in half

There is a neat rule. Let h = n >> 1, which is n / 2 rounded down.

• If n is even, n = 2h, so n * n = 4 * h * h.
• If n is odd, n = 2h + 1, so n * n = 4 * h * h + 4 * h + 1.

Times 4 is a left shift by 2. So we square the half, shift, and add a little. Each call cuts n in half.

class Solution {
    public static long square(long n) {
        if (n < 0) n = -n;
        if (n == 0) return 0;
        long h = n >> 1;                       // half of n, rounded down
        long s = square(h);                    // h * h
        if ((n & 1) == 0) return s << 2;       // even: 4 * h * h
        return (s << 2) + (h << 2) + 1;        // odd: 4 * h * h + 4 * h + 1
    }
}

This is also O(log n) time, but the waiting calls need O(log n) room on the call stack.

Watch out for

• Math.abs(Integer.MIN_VALUE) is still negative in int. Cast to long before taking the absolute value.
• Do not forget negative inputs. If you skip Math.abs, the test bits > 0 is false right away and you return 0 for -3.
• Zero must return 0. Both ways handle it because the loop never starts.

What interviewers ask next

• Multiply two different numbers a and b the same way? Yes. Read the bits of b and add shifted copies of a. This is called Russian peasant multiplication, and it is how simple chips multiply.
• Can you square with only adding odd numbers? Yes. 1 + 3 + 5 + ... + (2n - 1) equals n * n. Keep a running odd number and add 2 to it each step. That is O(n).
• What if the answer does not fit in a long? Use BigInteger, or return the answer modulo a big prime, adding and reducing at each step.
• Why is the shift loop faster? It does work per bit, not per unit. 1,000,000 has only 20 bits, so 20 rounds instead of a million adds.

Remember this

Grown-up words: the piles are partial products, doubling is a left shift, dropping the last bit is a right shift, and the whole method is shift and add multiplication, also called Russian peasant multiplication.