225. Calculate the Square of a Number Without Using *, /, or pow()

Given an integer n (which may be negative), compute n squared without using the *, /, or built-in power operators.

Input: A single line contains the integer n, which may be negative. Output: Print a single integer - n squared.

-10^4 <= n <= 10^4

Remember to handle the sign separately and work with the absolute value throughout - a square is always non-negative, so the sign of the original input never affects the final magnitude.

You need to compute a number times itself, but you're not allowed to use multiplication, division, or a power function at all - only addition and bit tricks. Brute force: Add n to a running total, n separate times (repeated addition) - this technically avoids the * operator, but takes O(n) additions, which is slow for large n and doesn't showcase real bit-manipulation understanding. Optimised: Since n times n is the same as adding n to itself, shifted appropriately, for every SET bit in n (because multiplying by 2^k is just a left-shift by k), you can build up n² using only a handful of shift-and-add operations - one per set bit in n, rather than one per unit of n's actual value.

Compute n * n using the same grade-school technique a multiplier circuit uses: decompose n into its binary bits, and for every set bit at position i, add (n left-shifted by i) to a running total, using only bitwise shifts and additions. Since n has only about log2(n) bits, this needs only that many shift-and-add steps instead of n additions, a large improvement when n is large (up to 10^4 here). Time: O(log n) Space: O(1)

Take the absolute value of n (to handle negatives, since squaring makes the sign irrelevant), then add n to a running total, n times, using a loop. This directly computes n * n as repeated addition without ever using the * operator, and is simple and obviously correct, but takes time proportional to n itself. Time: O(n) Space: O(1)

Use the algebraic identity for squares directly: if n is even, n^2 = 4 * (n/2)^2, computed via a right shift for the halving and a left shift by 2 for the multiply by 4; if n is odd, n^2 = 4 * ((n-1)/2)^2 + 4 * (n-1)/2 + 1 (expanding (2k+1)^2 = 4k^2 + 4k + 1), again using only shifts and additions. Recursing this way still takes O(log n) levels like the shift-and-add approach, but each level does a fixed, small number of operations (one shift, one conditional addition) rather than accumulating a partial sum across up to log n shifted values, making it a more direct and slightly leaner formulation of the same bound. Time: O(log n) Space: O(log n)

1. Take the absolute value of n first, since a square is always non-negative regardless of the original sign. 2. Think of n as a sum of powers of 2, based on which bits are set in its binary form (e.g. 5 = 4 + 1 = 2^2 + 2^0). 3. For each set bit at position k, you can add (n shifted left by k) to a running total - this is exactly what multiplication by a power of 2 means, achievable with just a bit shift and addition. 4. Sum up all these shifted contributions to get n times n.

Time: Proportional to the number of bits in n (roughly 32 or 64 steps at most) - essentially constant time regardless of how large n's actual value is. Space: O(1) - just a running total variable.

Test n = 0, a negative n (result must still be non-negative), and the extremes n = -10^4 and n = 10^4.

This problem is really testing whether you understand that multiplication by a power of 2 is just a bit shift - a foundational bit-manipulation insight that comes up in many other problems on this platform.