Bird
Raised Fist0
DSA Typescriptprogramming~5 mins

Check if Number is Power of Two in DSA Typescript - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Check if Number is Power of Two
O(1)
Understanding Time Complexity

We want to know how fast we can check if a number is a power of two. This helps us understand how the time needed grows as the number gets bigger.

The question is: How many steps does it take to decide if a number is a power of two?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


function isPowerOfTwo(n: number): boolean {
  if (n <= 0) return false;
  return (n & (n - 1)) === 0;
}

This code checks if a number is a power of two using a bitwise trick.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: A single bitwise AND operation and a subtraction.
  • How many times: Exactly once, no loops or recursion.
How Execution Grows With Input

Since the code does just one operation regardless of input size, the time stays the same even if the number grows.

Input Size (n)Approx. Operations
101
1001
10001

Pattern observation: The number of steps does not increase with input size; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means the check takes the same amount of time no matter how big the number is.

Common Mistake

[X] Wrong: "Checking if a number is a power of two requires looping through all bits or dividing repeatedly."

[OK] Correct: The bitwise trick does the check in one step without loops, so it is much faster.

Interview Connect

Knowing this quick check shows you understand how to use bitwise operations smartly, a skill that impresses in coding interviews.

Self-Check

What if we changed the input to be a string representing a binary number? How would the time complexity change?

Practice

(1/5)
1. What does it mean if a number is a power of two?
easy
A. It is divisible by 3
B. It is always an odd number
C. It can be written as 2 raised to some integer exponent
D. It is a prime number

Solution

  1. Step 1: Understand the definition of power of two

    A number is a power of two if it equals 2 raised to an integer exponent, like 2^0=1, 2^1=2, 2^2=4, etc.

  2. Step 2: Check other options

    Odd numbers, divisibility by 3, or primality do not define powers of two.

  3. Final Answer:

    It can be written as 2 raised to some integer exponent -> Option C

  4. Quick Check:

    Power of two = 2^n [OK]
Hint: Power of two means 2 multiplied by itself n times [OK]
Common Mistakes:
  • Thinking all powers of two are odd
  • Confusing powers of two with prime numbers
  • Assuming divisibility by 3 means power of two
2. Which of the following TypeScript expressions correctly checks if a number n is a power of two using bitwise operations?
easy
A. return n > 0 && (n & (n - 1)) === 0;
B. return n > 0 && (n | (n - 1)) === 0;
C. return n > 0 && (n & (n + 1)) === 0;
D. return n > 0 && (n ^ (n - 1)) === 0;

Solution

  1. Step 1: Understand the bitwise check for power of two

    The expression n & (n - 1) clears the lowest set bit. For powers of two, this results in zero.

  2. Step 2: Analyze each option

    return n > 0 && (n & (n - 1)) === 0; uses the correct bitwise AND with (n-1). Options A, B, and C use incorrect bitwise operators or operands.

  3. Final Answer:

    return n > 0 && (n & (n - 1)) === 0; -> Option A

  4. Quick Check:

    Bitwise AND with (n-1) = 0 means power of two [OK]
Hint: Use n & (n-1) === 0 to check power of two [OK]
Common Mistakes:
  • Using bitwise OR instead of AND
  • Using (n + 1) instead of (n - 1)
  • Forgetting to check n > 0
3. What will be the output of this TypeScript code?
function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}
console.log(isPowerOfTwo(16));
console.log(isPowerOfTwo(18));
medium
A. true true
B. false true
C. false false
D. true false

Solution

  1. Step 1: Check isPowerOfTwo(16)

    16 in binary is 10000. 16 & 15 (01111) = 0, so returns true.

  2. Step 2: Check isPowerOfTwo(18)

    18 in binary is 10010. 18 & 17 (10001) = 16 (not zero), so returns false.

  3. Final Answer:

    true false -> Option D

  4. Quick Check:

    16 is power of two, 18 is not [OK]
Hint: Check bitwise AND with (n-1) to confirm power of two [OK]
Common Mistakes:
  • Assuming 18 is power of two because it's even
  • Ignoring the n > 0 condition
  • Misreading bitwise AND results
4. Identify the error in this TypeScript function that checks if a number is a power of two:
function checkPower(n: number): boolean {
  return (n & (n - 1)) === 0;
}
medium
A. Missing check for n > 0 to avoid false positives
B. Incorrect bitwise operator used
C. Function should return number, not boolean
D. Parentheses are misplaced

Solution

  1. Step 1: Analyze the function logic

    The function uses bitwise AND correctly but does not check if n is positive.

  2. Step 2: Understand why n > 0 is needed

    Without n > 0, input 0 returns true incorrectly because 0 & -1 = 0.

  3. Final Answer:

    Missing check for n > 0 to avoid false positives -> Option A

  4. Quick Check:

    Check n > 0 before bitwise test [OK]
Hint: Always check n > 0 before bitwise power of two test [OK]
Common Mistakes:
  • Ignoring zero or negative inputs
  • Assuming bitwise alone is enough
  • Misunderstanding bitwise AND behavior
5. You want to filter an array of numbers to keep only those that are powers of two. Which TypeScript code snippet correctly does this?
const numbers = [0, 1, 2, 3, 4, 5, 8, 16, 18];
const powersOfTwo = numbers.filter(n => ???);
console.log(powersOfTwo);
hard
A. n >= 0 && (n | (n - 1)) === 0
B. n > 0 && (n & (n - 1)) === 0
C. n > 0 && (n & (n + 1)) === 0
D. n !== 0 && (n ^ (n - 1)) === 0

Solution

  1. Step 1: Understand the filter condition

    We want to keep numbers that are powers of two, so the condition must check n > 0 and bitwise AND with (n-1) equals zero.

  2. Step 2: Evaluate each option

    n > 0 && (n & (n - 1)) === 0 correctly uses the standard power of two check. Options B, C, and D use incorrect bitwise operations or conditions.

  3. Final Answer:

    n > 0 && (n & (n - 1)) === 0 -> Option B

  4. Quick Check:

    Filter with bitwise AND and n > 0 [OK]
Hint: Filter with n > 0 and n & (n-1) === 0 [OK]
Common Mistakes:
  • Using bitwise OR or XOR instead of AND
  • Not checking n > 0
  • Using (n + 1) instead of (n - 1)
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard