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

Problem Statement

Calculate the square of a number without using the multiplication operator (*), division operator (/), or the Math.pow() function.

Example:

Noob-Friendly Explanation

The square of a number n means n × n. But we can't use multiplication! So how do we do it?

Brute Force Idea: Addition is allowed! And multiplication is just repeated addition. So 5 × 5 = 5 + 5 + 5 + 5 + 5 = 25. We add n to itself n times.

Clever Bit Trick: We can use the fact that any number can be broken into powers of 2. For example, 5 = 4 + 1 = 2² + 2⁰. So 5 × 5 = 5 × (4 + 1) = 5×4 + 5×1 = 20 + 5 = 25. And multiplying by a power of 2 is just a left shift!

Approach 1: Brute Force (Repeated Addition)

Intuition

n × n is just n added to itself n times. We use a loop to perform repeated addition.

Algorithm

1. Take absolute value of n (since (-n)² = n²)
2. Add n to result, n times
3. Return result

class Solution {
    public static long square(int n) {
        // Square is same for positive and negative
        long num = Math.abs((long) n);
        long result = 0;

        for (long i = 0; i < num; i++) {
            result += num;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(square(5));   // 25
        System.out.println(square(8));   // 64
        System.out.println(square(-3));  // 9
        System.out.println(square(0));   // 0
        System.out.println(square(10));  // 100
    }
}

Complexity Analysis

• Time Complexity: O(N) — We loop N times, adding each time
• Space Complexity: O(1) — Only using a result variable

Approach 2: Optimal (Bit Manipulation / Russian Peasant Method)

Intuition

To compute n × n without *, treat the second n as a sum of powers of 2. For each set bit in n, shift the first n left by that bit position and add to the result.

This is based on binary multiplication:

• n × n = n × (bit_k × 2^k + ... + bit_1 × 2^1 + bit_0 × 2^0)
• For each set bit at position i: add n << i to the result

Algorithm

1. Take absolute value (square is always positive)
2. Let a = n (what we add) and b = n (whose bits we scan)
3. While b > 0:
   • If last bit of b is 1, add a to result
   • Left shift a by 1 (doubles it)
   • Right shift b by 1 (move to next bit)
4. Return result

class Solution {
    public static long square(int n) {
        long num = Math.abs((long) n);
        long result = 0;
        long addend = num; // this gets doubled each step

        long bits = num; // we scan bits of this

        while (bits > 0) {
            // If current bit is set, add the current addend
            if ((bits & 1) == 1) {
                result += addend;
            }
            // Double the addend (shift left)
            addend <<= 1;
            // Move to next bit (shift right)
            bits >>= 1;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(square(5));   // 25
        System.out.println(square(8));   // 64
        System.out.println(square(-3));  // 9
        System.out.println(square(0));   // 0
        System.out.println(square(10));  // 100
        System.out.println(square(100)); // 10000
    }
}

Complexity Analysis

• Time Complexity: O(log N) — We process each bit of N, and there are log₂(N) bits
• Space Complexity: O(1) — Only using a few variables

Bonus: Mathematical Approach (Odd Number Sum)

The square of n equals the sum of first n odd numbers: n² = 1 + 3 + 5 + 7 + ... + (2n - 1)

class Solution {
    public static long squareUsingOddSum(int n) {
        long num = Math.abs((long) n);
        long result = 0;
        for (long i = 0; i < num; i++) {
            result += (2 * i + 1); // uses multiplication, but illustrates the concept
        }
        return result;
    }
}

Key Takeaways

1. Binary Multiplication: Decompose one number into powers of 2 and add shifted values of the other
2. Left Shift = ×2: n << k is the same as n × 2^k, without using *
3. (-n)² = n²: Squaring always gives a positive result
4. Russian Peasant Method: This technique works for any multiplication, not just squaring