Bird
Raised Fist0
DSA Javaprogramming~5 mins

Check if Number is Power of Two in DSA Java - 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 the program can tell if a number is a power of two.

How does the time needed change as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


public boolean isPowerOfTwo(int n) {
    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 subtraction.
  • How many times: Exactly once, no loops or recursion.
How Execution Grows With Input

Since the code does only one check regardless of input size, the time stays the same.

Input Size (n)Approx. Operations
101
1001
10001

Pattern observation: The time does not increase as the number gets bigger.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Checking if a number is a power of two needs to check all smaller numbers or divide repeatedly."

[OK] Correct: This code uses a quick bit trick that does the check in one step without loops or division.

Interview Connect

Knowing this quick check shows you understand how bits work and can write fast code, a skill valued in many coding challenges.

Self-Check

"What if we changed the input to a long type instead of int? How would the time complexity change?"

Practice

(1/5)
1. Which of the following statements correctly describes a number that is a power of two?
easy
A. It is divisible by 3.
B. It is always an odd number.
C. It has exactly one bit set to 1 in its binary form.
D. It has all bits set to 1 in its binary form.

Solution

  1. Step 1: Understand binary representation of powers of two

    A power of two in binary has exactly one '1' bit and the rest are '0's, e.g., 4 is 100.

  2. Step 2: Check other options

    Odd numbers and divisibility by 3 do not define powers of two. Having all bits set to 1 is not a power of two.

  3. Final Answer:

    It has exactly one bit set to 1 in its binary form. -> Option C

  4. Quick Check:

    Power of two = single 1 bit [OK]
Hint: Power of two has only one '1' bit in binary [OK]
Common Mistakes:
  • Thinking all odd numbers are powers of two
  • Confusing powers of two with numbers having all bits set
  • Assuming divisibility by 3 means power of two
2. Which of the following Java code snippets correctly checks if an integer n is a power of two?
easy
A. return (n | (n - 1)) == 0;
B. return (n & (n - 1)) == 0;
C. return (n & (n + 1)) == 0;
D. return (n ^ (n - 1)) == 0;

Solution

  1. Step 1: Understand 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 other options

    Options A, C, and D use incorrect bitwise operations that do not correctly check power of two.

  3. Final Answer:

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

  4. Quick Check:

    Use n & (n-1) == 0 to check power of two [OK]
Hint: Use n & (n-1) == 0 to check power of two [OK]
Common Mistakes:
  • Using OR or XOR instead of AND in bitwise check
  • Checking n & (n + 1) which is incorrect
  • Not considering zero or negative numbers
3. What is the output of the following Java code? 
int n = 16;
boolean result = (n & (n - 1)) == 0;
System.out.println(result);
medium
A. true
B. Compilation error
C. false
D. Runtime exception

Solution

  1. Step 1: Calculate n & (n - 1) for n = 16

    16 in binary is 10000, 15 is 01111. Bitwise AND is 00000 (0).

  2. Step 2: Compare result to zero

    Since 16 & 15 == 0, the expression is true, so result is true.

  3. Final Answer:

    true -> Option A

  4. Quick Check:

    16 is power of two, so output is true [OK]
Hint: If n & (n-1) == 0, print true [OK]
Common Mistakes:
  • Confusing bitwise AND with OR
  • Expecting false for powers of two
  • Ignoring parentheses in expression
4. The following Java method is intended to check if a number is a power of two. What is the error? 
public static boolean isPowerOfTwo(int n) {
    return (n & n - 1) == 0;
}
medium
A. Method does not handle negative numbers.
B. Using bitwise OR instead of AND.
C. Incorrect return type.
D. Missing parentheses around (n - 1) causing wrong calculation.

Solution

  1. Step 1: Identify issue with negative numbers

    For n = Integer.MIN_VALUE (-2147483648), which is 0x80000000 in two's complement, n-1 = 0x7FFFFFFF (Integer.MAX_VALUE), and 0x80000000 & 0x7FFFFFFF == 0, so it incorrectly returns true.

  2. Step 2: Rule out other options

    Return type is correct, it uses AND (&), and operator precedence correctly parses as n & (n - 1) (no missing parentheses needed).

  3. Final Answer:

    Method does not handle negative numbers. -> Option A

  4. Quick Check:

    n > 0 && (n & (n-1)) == 0 [OK]
Hint: Include n > 0 to handle zero and negatives [OK]
Common Mistakes:
  • Not checking n > 0 before bitwise operation
  • Ignoring negative input handling
  • Confusing bitwise AND with OR
5. You want to write a Java method that returns true if a given positive integer n is a power of two, and false otherwise. Which of the following implementations correctly handles all positive integers including 1, and excludes zero and negative numbers?
hard
A. return n >= 0 && (n & (n + 1)) == 0;
B. return (n & (n - 1)) == 0;
C. return n != 0 && (n | (n - 1)) == 0;
D. return n > 0 && (n & (n - 1)) == 0;

Solution

  1. Step 1: Check for positive number condition

    Zero and negative numbers are not powers of two, so n > 0 is required.

  2. Step 2: Use bitwise check for power of two

    The expression (n & (n - 1)) == 0 correctly identifies powers of two including 1.

  3. Step 3: Analyze other options

    return (n & (n - 1)) == 0; misses positive check, allowing zero. Options C and D use incorrect bitwise operations.

  4. Final Answer:

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

  5. Quick Check:

    Check positive and n & (n-1) == 0 [OK]
Hint: Check n > 0 before bitwise test [OK]
Common Mistakes:
  • Not excluding zero and negative numbers
  • Using incorrect bitwise operators
  • Missing parentheses around (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