Log inSign up
mediumGeeksforGeeksNot Started

Square of a Number Without Multiplication

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer n, calculate and return its square (n^2) without using the multiplication operator (*), division operator (/), or the pow() function.

Example 1 · Example 1: Positive Integer:

Input: n = 5
Output: 25
Explanation: 5 in binary is 101. 5 * (22 + 20) = (5 << 2) + (5 << 0) = 20 + 5 = 25.

Example 2 · Example 2: Negative Integer:

Input: n = -7
Output: 49
Explanation: (-7)^2 = 72 = 49.

Example 3 · Example 3: Zero Input:

Input: n = 0
Output: 0
Explanation: 02 = 0.

Constraints:

  • -104 <= n <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Simulate multiplication using binary decomposition and bit shifts.
  • Analyze divide-and-conquer algebraic identities for squares of even and odd integers.
  • Maintain constant memory guarantees without standard math libraries.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Calculate square or product without *, /, or pow.
  • Synthesizing arithmetic operations via bit shifts.
  • Russian peasant multiplication variant.

Algorithmic Decision Tree:

  • Let num = abs(n).
  • While num > 0: if lowest bit is set, add (abs(n) << bitIndex) to result.
  • Advance bitIndex and shift num >>= 1.

Connected Patterns:

Divide Two Integers Without OperatorsSum of Two IntegersPower of Two

1. Repeated Addition

Intuition

Convert n to its absolute value a = abs(n). Add a to a running sum a times.

When to apply: Basic demonstration of multiplication definition.

Algorithm

  1. Step 1: a = abs(n), res = 0.
  2. Step 2: Loop i from 1 to a: res += a.
  3. Step 3: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6int squareBrute(int n) {
7 int a = abs(n);
8 int res = 0;
9 for (int i = 0; i < a; ++i) {
10 res += a;
11 }
12 return res;
13}
14
15int main() {
16 cout << "Brute (5): " << squareBrute(5) << endl; // 25
17 cout << "Brute (-7): " << squareBrute(-7) << endl; // 49
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

2. Recursive Bit Shift Halving

Intuition

Base case: if n == 0, return 0. If n < 0, n = -n. Let x = n >> 1. If n is even, return square(x) << 2. If n is odd, return (square(x) << 2) + (x << 2) + 1.

When to apply: When exploring recursive mathematical reductions.

Algorithm

  1. Step 1: If n == 0, return 0.
  2. Step 2: If n < 0, n = -n.
  3. Step 3: x = n >> 1.
  4. Step 4: If n & 1 == 0: return square(x) << 2.
  5. Step 5: Else: return (square(x) << 2) + (x << 2) + 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6int squareRecursive(int n) {
7 if (n == 0) return 0;
8 if (n < 0) n = -n;
9 int x = n >> 1;
10 if ((n & 1) == 0) {
11 return squareRecursive(x) << 2;
12 } else {
13 return (squareRecursive(x) << 2) + (x << 2) + 1;
14 }
15}
16
17int main() {
18 cout << "Recursive (5): " << squareRecursive(5) << endl; // 25
19 cout << "Recursive (-7): " << squareRecursive(-7) << endl; // 49
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(log n) recursion call stack

3. Binary Bit Expansion (Russian Peasant)

Intuition

Set pos = abs(n). Maintain temp = pos and shift = 0. While temp > 0, if temp & 1 is 1, add pos << shift to res. Shift temp >>= 1 and increment shift. Terminates in at most 31 bit-shift operations with strictly O(1) space.

When to apply: Optimal canonical solution for multiplying without *.

Algorithm

  1. Step 1: pos = abs(n), res = 0, shift = 0, temp = pos.
  2. Step 2: While temp > 0:
  3. Step 3: If temp & 1: res += (pos << shift).
  4. Step 4: shift++, temp >>= 1.
  5. Step 5: Return res.

Binary Shift Expansion Trace for n = 5 (101_2)

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Bit 0 of 5 is 1
Visual state
Values and pointers at this exact step
pointers
S
+5
0
↑ res = 5
Check / comparison
bit 0 is set
Decision / next transition
res += 5 << 0.
Why this step matters

Step 1: Bit 0 of 5 is 1. Add (5 << 0) = 5. res = 5.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6class Solution {
7public:
8 int calculateSquare(int n) {
9 if (n == 0) return 0;
10 long long pos = abs((long long)n);
11 long long temp = pos;
12 long long res = 0;
13 int shift = 0;
14
15 while (temp > 0) {
16 if (temp & 1) {
17 res += (pos << shift);
18 }
19 shift++;
20 temp >>= 1;
21 }
22 return (int)res;
23 }
24};
25
26int main() {
27 Solution sol;
28 cout << "Optimal (5): " << sol.calculateSquare(5) << endl; // 25
29 cout << "Optimal (-7): " << sol.calculateSquare(-7) << endl; // 49
30 cout << "Optimal (0): " << sol.calculateSquare(0) << endl; // 0
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Repeated AdditionO(n)O(1)Add abs(n) to a running total abs(n) times.Linear loop additions.
2.Better — Recursive Bit Shift HalvingO(log n)O(log n) call stackIf n is even, square(n) = square(n >> 1) << 2; if odd, (square(n >> 1) << 2) + ((n >> 1) << 2) + 1.Call stack recursion.
3.Optimal — Binary Bit-Shift Expansion (Russian Peasant)OptimalO(log n)O(1)Decompose n into set bits and accumulate (abs(n) << i) for each active bit i.Bitwise shifts and additions.

Common Pitfalls & Crucial Edge Cases

Using multiplication or division operators

The problem strictly bans *, /, and %.

Linear addition loop (adding n, n times)

O(n) addition triggers TLE for n >= 106.

32-bit integer overflow

Squaring numbers larger than 46340 overflows signed 32-bit int.

Crucial Edge Cases to Validate:

  • n = 0 — 02 = 0.
  • n = 1 or n = -1 — Returns 1.
  • Negative numbers (e.g. n = -5) — Must produce positive square 25.
  • Large n (e.g. n = 50000) — n2 = 2.5 * 109, which exceeds 32-bit signed integer limits. Use 64-bit integer (long long).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the binary representation identity: n^2 = sum(n << i) for every bit i set in n.
  2. Mention the recursive formula (2k)^2 = 4 * k^2 as an alternative divide-and-conquer strategy.
  3. Highlight 64-bit precision to prevent overflow when squaring.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does binary exponentiation allow squaring n in O(log n) bit shifts?

2.What recursive formula computes the square of n using bit manipulation?

3.How should negative inputs be handled when squaring?

Back to DSA Sheet