Check if Number is Even or Odd Using Bits in DSA Rust - 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 the bit check for even or odd numbers runs.

How does the time taken change as the number size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn is_even(num: u32) -> bool {
    (num & 1) == 0
}

fn is_odd(num: u32) -> bool {
    (num & 1) == 1
}
    

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

[OK] Correct: The code only looks at the last bit once, so the size of the number does not affect the time.

Interview Connect

Knowing this quick bit check shows you understand how computers use bits efficiently, a skill that helps in many coding problems.

Self-Check

"What if we checked multiple bits or all bits to find something else? 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 the least significant bit of the number

B. It checks if the number is greater than 1

C. It divides the number by 2

D. It adds 1 to the number

Solution

1. Step 1: Understand bitwise AND operation

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

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 the least significant bit of the number -> Option A

4. Quick Check:

   Least significant bit = odd/even check [OK]

Hint: Check last bit with & 1 to find odd or even fast [OK]

Common Mistakes:

• Thinking & 1 divides the number
• Confusing bitwise AND with addition
• Assuming it checks if number > 1

2. Which Rust code snippet correctly checks if a number n is odd using bitwise operations?

easy

A. if n ^ 1 == 1 { println!("Odd"); }

B. if n | 1 == 1 { println!("Odd"); }

C. if n & 0 == 1 { println!("Odd"); }

D. if n & 1 == 1 { println!("Odd"); }

Solution

1. Step 1: Identify correct bitwise operator for odd check

   The bitwise AND operator & with 1 isolates the least significant bit, which indicates oddness.

2. Step 2: Verify condition correctness

   Checking if n & 1 == 1 means the number is odd. Other operators like OR | or XOR ^ do not correctly check oddness.

3. Final Answer:

   if n & 1 == 1 { println!("Odd"); } -> Option D

4. Quick Check:

   Use & 1 == 1 to check odd [OK]

Hint: Use & 1 == 1 to check odd numbers in Rust [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Comparing with 0 instead of 1
• Using bitwise operators incorrectly

3. What will be the output of this Rust code?

let num = 14;
if num & 1 == 0 {
    println!("Even");
} else {
    println!("Odd");
}

medium

A. Even

B. Odd

C. 14

D. Compilation error

Solution

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

   Binary of 14 is 1110, and 1 is 0001. 1110 & 0001 = 0.

2. Step 2: Check condition and print output

   Since num & 1 == 0 is true, the code prints "Even".

3. Final Answer:

   Even -> Option A

4. Quick Check:

   14 & 1 = 0 means Even [OK]

Hint: If num & 1 equals 0, number is even [OK]

Common Mistakes:

• Assuming 14 is odd
• Confusing bitwise AND with arithmetic AND
• Expecting output to be the number itself

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

let n = 7;
if n & 1 = 1 {
    println!("Odd");
} else {
    println!("Even");
}

medium

A. Using & instead of && in if condition

B. Missing semicolon after println!

C. Using single = instead of == in if condition

D. Variable n is not declared

Solution

1. Step 1: Check the if condition syntax

   The condition uses single equals = which is assignment, not comparison.

2. Step 2: Correct the comparison operator

   It should use double equals == to compare n & 1 with 1.

3. Final Answer:

   Using single = instead of == in if condition -> Option C

4. Quick Check:

   Use == for comparison, not = [OK]

Hint: Use == for comparison, not = assignment [OK]

Common Mistakes:

• Confusing assignment (=) with equality (==)
• Thinking & is logical AND instead of bitwise
• Ignoring compiler error messages

5. Given a list of integers nums = [2, 3, 4, 5, 6], which Rust code correctly uses bitwise operations to filter only odd numbers and print them?

hard

A. for num in nums.iter() {
if num & 0 == 1 {
println!("{}", num);
}
}

B. for &num in &nums {
if num & 1 == 1 {
println!("{}", num);
}
}

C. for num in nums {
if num | 1 == 1 {
println!("{}", num);
}
}

D. for num in nums {
if num ^ 1 == 1 {
println!("{}", num);
}
}

Solution

1. Step 1: Understand iteration and bitwise odd check

   Iterate over references to numbers and use num & 1 == 1 to check odd numbers.

2. Step 2: Verify correct syntax and logic

   for &num in &nums { if num & 1 == 1 { println!("{}", num); } } correctly iterates with for &num in &nums and checks oddness with bitwise AND. Other options misuse operators or iteration.

3. Final Answer:

   for &num in &nums { if num & 1 == 1 { println!("{}", num); } } -> Option B

4. Quick Check:

   Use & 1 == 1 inside loop over &nums [OK]

Hint: Iterate references and use & 1 == 1 to print odd numbers [OK]

Common Mistakes:

• Using wrong bitwise operators like | or ^
• Iterating without references causing ownership errors
• Checking with & 0 instead of & 1