Check if Number is Power of Two in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Power of Two Check Function

What is the output of the following Go code that checks if a number is a power of two?

DSA Go

package main
import "fmt"

func isPowerOfTwo(n int) bool {
    return n > 0 && (n&(n-1)) == 0
}

func main() {
    fmt.Println(isPowerOfTwo(16))
    fmt.Println(isPowerOfTwo(18))
}

A

false
false

B

true
false

C

true
true

D

false
true

💡 Hint

Remember that a power of two has only one bit set in binary.

The function returns true only if n is greater than zero and n & (n-1) equals zero, which is true only for powers of two.

🧠 Conceptual

intermediate

Understanding Bitwise Check for Power of Two

Why does the expression (n & (n-1)) == 0 check if n is a power of two?

A Because powers of two have exactly one bit set, and subtracting 1 flips all bits after that bit, so ANDing results in zero.

B Because powers of two are always even numbers, and this expression checks evenness.

C Because (n-1) is always zero for powers of two, making the AND zero.

D Because this expression counts the number of set bits in n.

💡 Hint

Think about binary representation of powers of two and what subtracting 1 does.

A power of two has only one '1' bit. Subtracting 1 flips that bit and all bits after it, so ANDing n and n-1 clears the only set bit, resulting in zero.

🔧 Debug

advanced

Identify the Error in Power of Two Check

What error does the following Go code produce when checking if a number is a power of two?

DSA Go

package main
import "fmt"

func isPowerOfTwo(n int) bool {
    return n&(n-1) == 0
}

func main() {
    fmt.Println(isPowerOfTwo(0))
}

A Returns true incorrectly for 0

B Compilation error due to missing parentheses

C Runtime panic due to negative number

D Returns false correctly for 0

💡 Hint

Consider what happens when n is zero in the expression.

The function returns true for 0 because 0 & (0-1) equals 0, but zero is not a power of two. The check should include n > 0.

🚀 Application

advanced

Count Powers of Two in a List

Given a list of integers, which Go code correctly counts how many numbers are powers of two?

DSA Go

package main
import "fmt"

func isPowerOfTwo(n int) bool {
    return n > 0 && (n&(n-1)) == 0
}

func main() {
    nums := []int{1, 2, 3, 4, 5, 8, 16, 18}
    count := 0
    // Fill in counting logic here
    fmt.Println(count)
}

A

for _, n := range nums {
    if n > 0 {
        count++
    }
}

B

for i := 0; i < len(nums); i++ {
    if isPowerOfTwo(nums[i]) {
        count += nums[i]
    }
}

C

for _, n := range nums {
    if n&(n-1) == 0 {
        count++
    }
}

D

for _, n := range nums {
    if isPowerOfTwo(n) {
        count++
    }
}

💡 Hint

Use the provided isPowerOfTwo function correctly to count.

Option D correctly iterates over nums, uses isPowerOfTwo, and increments count. Option D adds values instead of count. Option D misses n > 0 check. Option D counts all positive numbers.

🧠 Conceptual

expert

Why is Zero Not a Power of Two?

Why is zero (0) not considered a power of two in computer science?

A Because zero is an even number, and powers of two must be odd.

B Because zero has no bits set in binary, so it cannot be a power of two.

C Because powers of two are defined as 2 raised to a non-negative integer exponent, and 2^x is never zero.

D Because zero causes overflow in bitwise operations.

💡 Hint

Think about the mathematical definition of powers of two.

Powers of two are numbers like 1, 2, 4, 8, ... which are 2 raised to some exponent. Zero is not in this sequence.

Practice

1. Which of the following statements correctly describes a number that is a power of two?

easy

A. It has exactly one bit set to 1 in its binary form.

B. It is always an odd number.

C. It is divisible by 3.

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. For example, 4 is 100 in binary.

2. Step 2: Analyze the options

   The statement "It has exactly one bit set to 1 in its binary form" matches the binary property of powers of two. The other options do not: powers of two (except 1) are even, not divisible by 3, and do not have all bits set to 1.

3. Final Answer:

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

4. Quick Check:

   Power of two = one '1' bit [OK]

Hint: Power of two has only one '1' bit in binary [OK]

Common Mistakes:

• Thinking powers of two are always odd
• Confusing powers of two with numbers divisible by 3
• Assuming all bits are set to 1

2. Which of the following Go code snippets correctly checks if an integer n is a power of two?

easy

A. if n & (n + 1) == 0 { /* power of two */ }

B. if n | (n - 1) == 0 { /* power of two */ }

C. if n & (n - 1) == 0 { /* power of two */ }

D. if n ^ (n - 1) == 0 { /* power of two */ }

Solution

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

   The expression n & (n - 1) == 0 is true only if n is a power of two (and n > 0).

2. Step 2: Analyze each option

   The snippet if n & (n - 1) == 0 { /* power of two */ } uses the correct bitwise AND operation. The others use incorrect bitwise operations that do not correctly check for power of two.

3. Final Answer:

   if n & (n - 1) == 0 { /* power of two */ } -> Option C

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 bitwise OR instead of AND
• Using n + 1 instead of n - 1
• Using XOR which does not work here

3. What is the output of the following Go code?

package main
import "fmt"
func main() {
    n := 16
    if n > 0 && (n & (n - 1)) == 0 {
        fmt.Println("Power of Two")
    } else {
        fmt.Println("Not Power of Two")
    }
}

medium

A. Runtime Error

B. Power of Two

C. Compilation Error

D. Not Power of Two

Solution

1. Step 1: Evaluate the condition for n = 16

   16 in binary is 10000. 16 - 1 = 15 (binary 01111). Bitwise AND: 10000 & 01111 = 0.

2. Step 2: Check the if condition

   Since n > 0 and bitwise AND is 0, the condition is true, so it prints "Power of Two".

3. Final Answer:

   Power of Two -> Option B

4. Quick Check:

   16 & 15 == 0 means power of two [OK]

Hint: Check if n & (n-1) == 0 and n > 0 [OK]

Common Mistakes:

• Ignoring n > 0 check
• Misunderstanding bitwise AND result
• Assuming all even numbers are powers of two

4. The following Go code is intended to check if n is a power of two. What is the error?

func isPowerOfTwo(n int) bool {
    return n & (n - 1) == 0
}

medium

A. The function should return an integer, not bool.

B. The bitwise AND operator is used incorrectly.

C. The parentheses around n - 1 are unnecessary and cause error.

D. It does not handle the case when n is zero or negative.

Solution

1. Step 1: Understand the function logic

   The expression n & (n - 1) == 0 returns true for powers of two and also for zero.

2. Step 2: Identify missing check

   Zero and negative numbers are not powers of two, but this function returns true for zero. It lacks a check for n > 0.

3. Final Answer:

   It does not handle the case when n is zero or negative. -> Option D

4. Quick Check:

   Check n > 0 before bitwise test [OK]

Hint: Always check n > 0 before bitwise power of two test [OK]

Common Mistakes:

• Not checking for n > 0
• Misusing bitwise operators
• Assuming parentheses cause error

5. You want to write a Go function that returns true if a number n is a power of two, but also handles zero and negative inputs correctly. Which of the following implementations is correct?

hard

A. func isPowerOfTwo(n int) bool {
return n > 0 && (n & (n - 1)) == 0
}

B. func isPowerOfTwo(n int) bool {
return n >= 0 && (n | (n - 1)) == 0
}

C. func isPowerOfTwo(n int) bool {
return n != 0 && (n & (n + 1)) == 0
}

D. func isPowerOfTwo(n int) bool {
return (n & (n - 1)) == 1
}

Solution

1. Step 1: Check for positive input

   The function must ensure n is greater than zero to exclude zero and negatives.

2. Step 2: Use correct bitwise condition

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

3. Step 3: Analyze options

   The implementation func isPowerOfTwo(n int) bool { return n > 0 && (n & (n - 1)) == 0 } correctly combines both checks. The others use incorrect operators or conditions.

4. Final Answer:

   func isPowerOfTwo(n int) bool { return n > 0 && (n & (n - 1)) == 0 } -> Option A

5. Quick Check:

   Check n > 0 and n & (n-1) == 0 [OK]

Hint: Check n > 0 and n & (n-1) == 0 for power of two [OK]

Common Mistakes:

• Using bitwise OR instead of AND
• Not checking n > 0
• Using wrong bitwise expressions