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

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

O(1)

Understanding Time Complexity

We want to know 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.

public class EvenOddChecker {
    public static boolean isEven(int num) {
        return (num & 1) == 0;
    }
}
    

This code checks if a number is even by looking at its last bit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise AND operation on the number's last bit.
• How many times: Exactly once per check.

How Execution Grows With Input

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

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

Pattern observation: The time stays the same even if the number grows.

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 bits takes longer for bigger numbers because they have more bits."

[OK] Correct: The operation only looks at the last bit, so it always takes the same time.

Interview Connect

Knowing this quick bit check shows you understand how computers use bits, which is a handy skill in many coding problems.

Self-Check

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

Practice

1. What does the expression num & 1 check when determining if a number is even or odd?

easy

A. It checks if the least significant bit of num is 1, indicating odd number

B. It checks if num is greater than 1

C. It shifts num one bit to the right

D. It adds 1 to num

Solution

1. Step 1: Understand bitwise AND operation

   The expression num & 1 performs a bitwise AND between num and 1, which isolates the least significant bit (rightmost bit) of num.

2. Step 2: Interpret the least significant bit

   If the least significant bit is 1, the number is odd; if it is 0, the number is even.

3. Final Answer:

   It checks if the least significant bit of num is 1, indicating odd number -> Option A

4. Quick Check:

   num & 1 = 1 means odd [OK]

Hint: Check last bit with & 1; 1 means odd, 0 means even [OK]

Common Mistakes:

• Thinking & 1 shifts bits instead of checking last bit
• Confusing bitwise AND with addition
• Assuming & 1 checks if number is greater than 1

2. Which of the following Java code snippets correctly checks if an integer num is even using bitwise operators?

easy

A. if ((num & 0) == 1) { System.out.println("Even"); }

B. if ((num | 1) == 0) { System.out.println("Even"); }

C. if ((num & 1) == 0) { System.out.println("Even"); }

D. if ((num ^ 1) == 0) { System.out.println("Even"); }

Solution

1. Step 1: Analyze bitwise AND with 1

   The expression num & 1 isolates the least significant bit. If it equals 0, the number is even.

2. Step 2: Check correctness of conditions

   if ((num & 1) == 0) { System.out.println("Even"); } correctly checks if (num & 1) == 0 to print "Even". Other options misuse bitwise OR, AND with 0, or XOR, which do not correctly check evenness.

3. Final Answer:

   if ((num & 1) == 0) { System.out.println("Even"); } -> Option C

4. Quick Check:

   num & 1 == 0 means even [OK]

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

Common Mistakes:

• Using bitwise OR instead of AND
• Comparing with wrong values like 1 when checking even
• Using XOR incorrectly for even check

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

int num = 7;
if ((num & 1) == 0) {
    System.out.println("Even");
} else {
    System.out.println("Odd");
}

medium

A. Compilation error

B. Even

C. 0

D. Odd

Solution

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

   7 in binary is 0111. 0111 & 0001 = 0001, which equals 1.

2. Step 2: Check condition and print output

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

3. Final Answer:

   Odd -> Option D

4. Quick Check:

   7 & 1 = 1 means odd [OK]

Hint: If num & 1 equals 1, print Odd; else Even [OK]

Common Mistakes:

• Assuming 7 is even
• Confusing bitwise AND with arithmetic AND
• Expecting output 0 or error

4. Identify the error in the following Java code that tries to check if a number is odd using bits:

int num = 10;
if (num & 1 == 1) {
    System.out.println("Odd");
} else {
    System.out.println("Even");
}

medium

A. No error, code is correct

B. Missing parentheses around (num & 1)

C. Incorrect variable type for num

D. Using bitwise OR instead of AND

Solution

1. Step 1: Analyze operator precedence in condition

   In Java, == has higher precedence than &. So num & 1 == 1 is treated as num & (1 == 1).

2. Step 2: Fix condition with parentheses

   Since (1 == 1) is true (boolean), num & true is invalid. Correct syntax is (num & 1) == 1.

3. Final Answer:

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

4. Quick Check:

   Use parentheses to ensure correct bitwise operation [OK]

Hint: Always parenthesize bitwise ops before comparison [OK]

Common Mistakes:

• Ignoring operator precedence causing syntax errors
• Using bitwise OR instead of AND
• Assuming code compiles without parentheses

5. You want to write a Java method isEven(int num) that returns true if num is even and false if odd, using bitwise operators. Which implementation is correct?

hard

A. public boolean isEven(int num) { return (num & 1) == 0; }

B. public boolean isEven(int num) { return (num | 1) == 0; }

C. public boolean isEven(int num) { return (num ^ 1) == 0; }

D. public boolean isEven(int num) { return (num & 0) == 1; }

Solution

1. Step 1: Understand bitwise check for even

   Even numbers have least significant bit 0, so (num & 1) == 0 returns true for even numbers.

2. Step 2: Evaluate each option

   public boolean isEven(int num) { return (num & 1) == 0; } correctly returns true if num is even. Options A, B, and D use incorrect bitwise operations that do not reliably check evenness.

3. Final Answer:

   public boolean isEven(int num) { return (num & 1) == 0; } -> Option A

4. Quick Check:

   Use (num & 1) == 0 to return true for even [OK]

Hint: Return (num & 1) == 0 for even check in method [OK]

Common Mistakes:

• Using bitwise OR or XOR incorrectly
• Comparing with wrong values
• Returning wrong boolean for even check