Understanding the Problem

The problem at hand is to count the number of odd and even elements in an array. Given an array of integers, the goal is to determine how many of these integers are odd and how many are even.

Let's consider an example:

int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

In this array, there are 5 odd numbers (1, 3, 5, 7, 9) and 5 even numbers (2, 4, 6, 8, 10).

Algorithms

Simple Iteration:

• Iterate through the array.
• Use the modulus operator (%) to check if each element is divisible by 2.
• Count odd and even numbers accordingly.

Bitwise AND:

• Use bitwise AND operation with 1 to check the least significant bit.
• If the result is 0, the number is even; it it's 1, the number is odd.

Code Implementation

Simple Iteration:

#include <iostream>

void countOddEvenSimpleIteration(const int numbers[], int arraySize) {
    int countOdd = 0, countEven = 0;
    
    for (int i = 0; i < arraySize; ++i) {
        if (numbers[i] % 2 == 0) {
            // Even number
            countEven++;
        } else {
            // Odd number
            countOdd++;
        }
    }

    std::cout << "Odd numbers: " << countOdd << std::endl;
    std::cout << "Even numbers: " << countEven << std::endl;
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int arraySize = sizeof(numbers) / sizeof(numbers[0]);

    countOddEvenSimpleIteration(numbers, arraySize);

    return 0;
}

Bitwise AND:

#include <iostream>

void countOddEvenBitwiseAnd(const int numbers[], int arraySize) {
    int countOdd = 0, countEven = 0;
    
    for (int i = 0; i < arraySize; ++i) {
        if (numbers[i] & 1) {
            // Odd number
            countOdd++;
        } else {
            // Even number
            countEven++;
        }
    }

    std::cout << "Odd numbers: " << countOdd << std::endl;
    std::cout << "Even numbers: " << countEven << std::endl;
}

int main() {
    int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int arraySize = sizeof(numbers) / sizeof(numbers[0]);

    countOddEvenBitwiseAnd(numbers, arraySize);

    return 0;
}

Complexity Analysis

Simple Iteration:

• Time Complexity: O(n) - The algorithm iterates through each element of the array exactly once, making it a linear time complexity algorithm where “n” the size of the array.
• Space Complexity: O(1) - The algorithm uses a constant amount of additional space regardless of the size of the input array. It only uses fixed number of variables (countOdd and countEven) to store the counts.

Bitwise AND:

• Time Complexity: O(n) - Similar to the simple iteration, the algorithm iterates through each element of the array once, making it a linear time complexity algorithm where “n” is the size of the array.
• Space Complexity: O(1) - Like the simple iteration, the algorithm uses a constant amount of additional space.