Print Even - Odd in C++ (Time Complexity: O(n))

Given a positive integer n, for each number from 0 to n - 1, print "odd" if the number is odd or the number itself if it is even.

Example:

Input: n = 6
Output (console):
0
odd
2
odd
4
odd

Note:

You have to print to the console, your function shouldn't return anything.

Understanding the Problem

The core challenge of this problem is to iterate through a range of numbers and determine whether each number is odd or even. If the number is even, we print the number itself; if it is odd, we print the string "odd". This problem is straightforward but helps in understanding basic control structures and conditional statements in programming.

Approach

To solve this problem, we can use a simple loop to iterate through the numbers from 0 to n-1. For each number, we check if it is even or odd using the modulus operator (%). If the number is even (i.e., number % 2 == 0), we print the number. Otherwise, we print "odd".

Naive Solution

The naive solution involves iterating through each number and using an if-else statement to check if the number is even or odd. This approach is already optimal for this problem since it runs in O(n) time complexity, where n is the input number.

Optimized Solution

Given the simplicity of the problem, the naive solution is already optimal. There are no further optimizations needed for this specific problem.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Start a loop from 0 to n-1.
For each number in the loop, check if it is even or odd using the modulus operator (%).
If the number is even, print the number.
If the number is odd, print "odd".

Code Implementation


#include <iostream>  // Include the iostream library for input and output

// Function to print "odd" or the number itself based on whether the number is odd or even
void printEvenOdd(int n) {
    for (int i = 0; i < n; ++i) {  // Loop from 0 to n-1
        if (i % 2 == 0) {  // Check if the number is even
            std::cout << i << std::endl;  // Print the number if it is even
        } else {
            std::cout << "odd" << std::endl;  // Print "odd" if the number is odd
        }
    }
}

// Main function
int main() {
    int n = 6;  // Example input
    printEvenOdd(n);  // Call the function with the example input
    return 0;  // Return 0 to indicate successful execution
}

Complexity Analysis

The time complexity of this solution is O(n) because we are iterating through the numbers from 0 to n-1 exactly once. The space complexity is O(1) as we are not using any additional space that scales with the input size.

Edge Cases

Potential edge cases include:

n = 0: The function should handle this gracefully by not printing anything.
n = 1: The function should print "0" since 0 is even.

These edge cases are handled naturally by the loop structure and conditional checks.

Testing

To test the solution comprehensively, consider the following test cases:

n = 0: No output.
n = 1: Output should be "0".
n = 6: Output should be "0\nodd\n2\nodd\n4\nodd".
n = 10: Output should be "0\nodd\n2\nodd\n4\nodd\n6\nodd\n8\nodd".

These test cases cover a range of inputs from the smallest to larger values.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem statement and constraints clearly.
Break down the problem into smaller, manageable parts.
Think about edge cases and how to handle them.
Write clean and readable code with comments to explain your logic.

Practicing similar problems and studying basic algorithms can help improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of printing "odd" or the number itself based on whether the number is odd or even. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong programming skills.

Additional Resources

For further reading and practice, consider the following resources: