Check if Number is Even or Odd Using Bits in DSA C++ - Time & Space Complexity

Time Complexity: Check if Number is Even or Odd Using Bits

O(1)

Understanding Time Complexity

We want to understand how fast we can check if a number is even or odd using bits.

How does the time to check change as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool isEven(int num) {
    return (num & 1) == 0;
}
    

This code uses a bitwise AND to check the last bit of the number to decide if it is even or odd.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single bitwise AND operation.
• How many times: Exactly once per function call.

How Execution Grows With Input

The operation always takes the same amount of time no matter how big the number is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays constant regardless of input size.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Checking even or odd takes longer for bigger numbers because the number has more digits."

[OK] Correct: The bitwise operation looks only at the last bit, so it does not depend on the size of the number.

Interview Connect

Knowing this quick bit trick shows you understand how computers work with numbers at a low level, which is a useful skill in many coding problems.

Self-Check

"What if we checked if a number is divisible by 4 using bits? How would the time complexity change?"

Practice

1. Which bit operation can be used to check if a number is even or odd?

easy

A. Check the least significant bit using AND with 1

B. Shift the number right by 1

C. XOR the number with 1

D. Invert all bits of the number

Solution

1. Step 1: Understand the least significant bit (LSB)

   The LSB of a binary number determines if it is even or odd. If LSB is 0, number is even; if 1, number is odd.

2. Step 2: Use AND operation with 1 to check LSB

   Performing bitwise AND with 1 isolates the LSB. Result 0 means even, 1 means odd.

3. Final Answer:

   Check the least significant bit using AND with 1 -> Option A

4. Quick Check:

   LSB & 1 = 0 (even) or 1 (odd) [OK]

Hint: Use n & 1 to check even or odd quickly [OK]

Common Mistakes:

• Using XOR instead of AND to check LSB
• Checking the most significant bit instead
• Using bit shift without checking bits

2. Which of the following C++ code snippets correctly checks if num is odd using bits?

easy

A. if ((num & 1) == 0) { /* odd */ }

B. if ((num >> 1) == 1) { /* odd */ }

C. if ((num ^ 1) == 1) { /* odd */ }

D. if ((num & 1) == 1) { /* odd */ }

Solution

1. Step 1: Understand bitwise AND with 1

   Using (num & 1) extracts the least significant bit. If it equals 1, number is odd.

2. Step 2: Check condition for odd number

   The condition (num & 1) == 1 correctly identifies odd numbers.

3. Final Answer:

   if ((num & 1) == 1) { /* odd */ } -> Option D

4. Quick Check:

   (num & 1) == 1 means odd [OK]

Hint: Use (num & 1) == 1 to check odd numbers [OK]

Common Mistakes:

• Using == 0 to check odd (actually checks even)
• Using bit shift without comparison
• Using XOR incorrectly for odd check

3. What is the output of the following C++ code?

int num = 14;
if (num & 1) {
    std::cout << "Odd";
} else {
    std::cout << "Even";
}

medium

A. Odd

B. Even

C. 14

D. Error

Solution

1. Step 1: Evaluate bitwise AND of num and 1

   14 in binary is 1110. The least significant bit is 0. So, 14 & 1 = 0.

2. Step 2: Check the if condition

   Since (num & 1) is 0, the else block executes, printing "Even".

3. Final Answer:

   Even -> Option B

4. Quick Check:

   14 & 1 = 0 means Even [OK]

Hint: Check LSB: 0 means even, 1 means odd [OK]

Common Mistakes:

• Assuming 14 is odd because it ends with 4
• Confusing bitwise AND with arithmetic AND
• Printing num instead of "Even" or "Odd"

4. Identify the error in the following code snippet that checks if a number is odd:

int num = 7;
if (num & 1 == 1) {
    std::cout << "Odd";
} else {
    std::cout << "Even";
}

medium

A. Incorrect variable type for num

B. Using == instead of =

C. Missing parentheses around (num & 1)

D. No error, code is correct

Solution

1. Step 1: Analyze operator precedence in condition

   In C++, == has higher precedence than &. So, num & 1 == 1 is parsed as num & (1 == 1), which is num & 1. This is not the intended comparison.

2. Step 2: Identify the error

   Without parentheses, the expression does not explicitly compare (num & 1) to 1, which can cause confusion or unintended behavior. Parentheses are needed: (num & 1) == 1.

3. Final Answer:

   Missing parentheses around (num & 1) -> Option C

4. Quick Check:

   Operator precedence requires parentheses for clarity [OK]

Hint: Use parentheses: (num & 1) == 1 to avoid precedence issues [OK]

Common Mistakes:

• Misinterpreting operator precedence (== > &)
• Thinking parentheses are not needed
• Believing the code works correctly without parentheses

5. You want to write a function in C++ that returns true if a number is even and false if odd, using bitwise operations. Which of the following implementations is correct?

hard

A. bool isEven(int n) { return (n & 1) == 0; }

B. bool isEven(int n) { return (n & 1) == 1; }

C. bool isEven(int n) { return (n >> 1) == 0; }

D. bool isEven(int n) { return !(n ^ 1); }

Solution

1. Step 1: Understand even number bit pattern

   Even numbers have least significant bit 0. So (n & 1) == 0 means even.

2. Step 2: Check each function implementation

   bool isEven(int n) { return (n & 1) == 1; } returns true for odd numbers, so incorrect. bool isEven(int n) { return (n & 1) == 0; } correctly returns true for even numbers. Options C and D do not correctly check evenness.

3. Final Answer:

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

4. Quick Check:

   Even if LSB is 0 [OK]

Hint: Return (n & 1) == 0 for even check [OK]

Common Mistakes:

• Returning true for odd numbers by mistake
• Using bit shift incorrectly for even check
• Using XOR without understanding its effect