Skip to main content

Array Basics

Separate Odd and Even Elements of an Array

When working with arrays, there are situations where we may need to separate elements based on specific criteria, one of the most common of such criteria is whether they are odd or even. In such cases, it's common to create two separate arrays: one for odd elements and one for even elements. By doing this, we can process or analyze odd and even elements independently, ensuring that the original array remains unchanged. This approach allows us to work with the separated elements while preserving the original array for future use.

Write a program that takes an array as input and creates two separate arrays: One containing all the odd elements and the other containing all the even elements.

Example

Input: nums = [4, 8, 15, 16, 23, 42]
Output:
Odd elements: [15, 23]              
Even elements: [4, 8, 16, 42]
Explanation: The original array is split into two arrays: one containing the odd elements [15,23] and the other containing the even elements [4, 8, 16, 42].

Input: nums = [10, 21, 30, 43, 52]
Output:
Odd elements: [21, 43]             
Even elements: [10, 30, 52]

Approach

The task is to create two separate arrays: one for odd elements and another for even elements. To achieve this, we first need to determine the size of these two arrays, which depends on the count of odd and even elements in the original array, nums.
We start by iterating through nums to count the number of odd and even elements. After counting, we can declare two new arrays: odd_nums and even_nums. The size of odd_nums will be equal to the count of odd elements, and the size of even_nums will be equal to the count of even elements. Now, we need two variables, odd_index and even_index, both initialized to 0.

Why Do We Need These Variables?

These variables act as counters that tell us the current position in the odd_nums and even_nums arrays. Without them, we wouldn't know where to place the next odd or even element as we iterate through the original array.

Why Initialize to 0?

We initialize odd_index and even_index to 0 because arrays in most programming languages, including C++, start indexing from 0. This means the first element in an array is at position 0. By starting these variables at 0, we ensure that the first odd or even element will be placed at the beginning of the respective array.
Now, Iterate through the original array nums again. For each element, Check if the element is odd or even:

  • If the element is even (nums[index] % 2 == 0), assign it to the even_nums array at the position indicated by even_index, and then increment the even_index pointer by 1.
  • If the element is odd(nums[index] % 2 == 1), assign it to the odd_nums array at the position indicated by odd_index, and then increment the odd_index pointer by 1.

Why Increment by 1 Every Time?

Every time we add an element to either odd_nums or even_nums, we increment the respective variable (odd_index or even_index) by 1. This ensures that the next element is placed in the next available position in the array. If we didn't increment the variables, we would overwrite the previous element in the array, which would lead to incorrect results.
After completing the iteration, the odd_nums array will contain all the odd elements from the original array, and the even_nums array will contain all the even elements. Print them them in separate lines.

Dry Run

Input: nums = [4, 8, 15, 16, 23, 42]

  1. Initialization:
    odd_count = 0
    even_count = 0
  2. First Loop - Counting Odd and Even Elements:
    We loop through the nums array and count odd and even numbers:After the loop:
    • nums[0] = 4 → Even, so increment even_count to 1.
    • nums[1] = 8 → Even, so increment even_count to 2.
    • nums[2] = 15 → Odd, so increment odd_count to 1.
    • nums[3] = 16 → Even, so increment even_count to 3.
    • nums[4] = 23 → Odd, so increment odd_count to 2.
    • nums[5] = 42 → Even, so increment even_count to 4.

      odd_count = 2
      even_count = 4
  4. Create Arrays for Odd and Even Elements:
    Create odd_nums[2] and even_nums[4] to store the odd and even elements.
  5. Second Loop - Separating Odd and Even Elements:
    We loop through the nums array again to separate the odd and even elements:After the loop:
    • nums[0] = 4 → Even, so add to even_nums[0], even_index increments to 1.
    • nums[1] = 8 → Even, so add to even_nums[1], even_index increments to 2.
    • nums[2] = 15 → Odd, so add to odd_nums[0], odd_index increments to 1.
    • nums[3] = 16 → Even, so add to even_nums[2], even_index increments to 3.
    • nums[4] = 23 → Odd, so add to odd_nums[1], odd_index increments to 2.
    • nums[5] = 42 → Even, so add to even_nums[3], even_index increments to 4.

      odd_nums = [15, 23]
      even_nums = [4, 8, 16, 42]
  7. Output:
    Print Odd elements: [15, 23]
    Print Even elements: [4, 8, 16, 42]

Final Output:
Odd elements: [15, 23]
Even elements: [4, 8, 16, 42]

0:00
/1:54
Code for All Languages
C++ 
#include <iostream>
using namespace std;

// Function to separate odd and even elements
void separateOddEven(int nums[], int size) {
    int odd_count = 0, even_count = 0;

    // Count odd and even elements
    for (int index = 0; index < size; ++index) {
        if (nums[index] % 2 == 0) {
            ++even_count;
        } 
        else {
            ++odd_count;
        }
    }

    int odd_nums[odd_count];
    int even_nums[even_count];
    int odd_index = 0, even_index = 0;

    // Separate elements into odd and even arrays
    for (int index = 0; index < size; ++index) {
        if (nums[index] % 2 == 0) {
            even_nums[even_index++] = nums[index];
        } 
        else {
            odd_nums[odd_index++] = nums[index];
        }
    }

    // Print the elements of the odd array
    cout << "Odd elements: ";
    for (int index = 0; index < odd_count; ++index) {
        cout << odd_nums[index] << " ";
    }
    cout << endl;

    // Print the elements of the even array
    cout << "Even elements: ";
    for (int index = 0; index < even_count; ++index) {
        cout << even_nums[index] << " ";
    }
    cout << endl;
}

Java 
import java.util.Scanner;

public class LearnYard {
    // Function to separate odd and even elements
    public static void separateOddEven(int[] nums, int size) {
        int oddCount = 0, evenCount = 0;

        // Count odd and even elements
        for (int i = 0; i < size; ++i) {
            if (nums[i] % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }

        int[] oddNums = new int[oddCount];
        int[] evenNums = new int[evenCount];
        int oddIndex = 0, evenIndex = 0;

        // Separate elements into odd and even arrays
        for (int i = 0; i < size; ++i) {
            if (nums[i] % 2 == 0) {
                evenNums[evenIndex++] = nums[i];
            } 
            else {
                oddNums[oddIndex++] = nums[i];
            }
        }

        // Print the elements of the odd array
        System.out.print("Odd elements: ");
        for (int i = 0; i < oddCount; ++i) {
            System.out.print(oddNums[i] + " ");
        }
        System.out.println();

        // Print the elements of the even array
        System.out.print("Even elements: ");
        for (int i = 0; i < evenCount; ++i) {
            System.out.print(evenNums[i] + " ");
        }
        System.out.println();
    }
}

Python 
# Function to separate odd and even elements
def separateOddEven(nums, size):
    odd_count = 0
    even_count = 0

    # Count odd and even elements
    for num in nums:
        if num % 2 == 0:
            even_count += 1
        else:
            odd_count += 1

    odd_nums = [0] * odd_count
    even_nums = [0] * even_count
    odd_index = 0
    even_index = 0

    # Separate elements into odd and even arrays
    for num in nums:
        if num % 2 == 0:
            even_nums[even_index] = num
            even_index += 1
        else:
            odd_nums[odd_index] = num
            odd_index += 1

    # Print the elements of the odd array
    print("Odd elements:", " ".join(map(str, odd_nums)))

    # Print the elements of the even array
    print("Even elements:", " ".join(map(str, even_nums)))

Javascript 
// Function to separate odd and even elements
function separateOddEven(nums, size) {
    let odd_count = 0, even_count = 0;

    // Count odd and even elements
    for (let i = 0; i < size; ++i) {
        if (nums[i] % 2 === 0) {
            even_count++;
        } else {
            odd_count++;
        }
    }

    let odd_nums = new Array(odd_count);
    let even_nums = new Array(even_count);
    let odd_index = 0, even_index = 0;

    // Separate elements into odd and even arrays
    for (let i = 0; i < size; ++i) {
        if (nums[i] % 2 === 0) {
            even_nums[even_index++] = nums[i];
        } else {
            odd_nums[odd_index++] = nums[i];
        }
    }

    // Print the elements of the odd array
    console.log("Odd elements: " + odd_nums.join(" "));

    // Print the elements of the even array
    console.log("Even elements: " + even_nums.join(" "));
}

Time Complexity : O(n)

The time complexity of the approach is determined by the two iterations over the array nums.

  1. First Iteration (Counting Elements): We first iterate through each element of nums to count the number of odd and even elements. If n is the size of the array nums, this loop runs n times, and each counting operation takes constant time, O(1).
  2. Second Iteration (Separating Elements): We then iterate through each element of nums again to place them into the odd_nums and even_nums arrays. This loop also runs n times, and each assignment operation (e.g., odd_nums[odd_index] = nums[i]) takes constant time, O(1).

Since both loops run independently, the total time complexity is O(n) + O(n) = O(n).

Space Complexity : O(n)

Total Space Complexity: O(n)

  1. Input Array (nums):
    The input array nums contains n elements, so it takes up O(n) space.
  2. New Arrays (odd_nums and even_nums):
    Two new arrays, odd_nums and even_nums, are created to store the odd and even elements respectively.
    • The size of odd_nums is proportional to the number of odd elements, and the size of even_nums is proportional to the number of even elements.
    • Together, these two arrays will store all n elements from the original array nums. Therefore, the space required for these arrays is O(n).

Thus, the total space used by the algorithm, including the input and the new arrays, is O(n).

Auxiliary Space Complexity: O(n)

Auxiliary space refers to the extra space used by the algorithm excluding the input data.

  1. New Arrays (odd_nums and even_nums):
    These two arrays are used to store the separated odd and even elements. Their combined size is O(n), as they store all elements of the original array.
  2. Other Variables:
    The algorithm uses a few additional variables like odd_count, even_count, odd_index, and even_index, which only require constant space O(1).

Since the primary extra space used by the algorithm is for the odd_nums and even_nums arrays, the auxiliary space complexity is O(n).