Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C++

Solution: Remove Even Integers From Array

Explore how to remove even integers from an array in C++ by traversing the array and creating a new array of odd integers. Understand the solution’s O(n) time complexity and O(1) space complexity, preparing you for interview coding challenges involving array manipulation.

We'll cover the following...

Statement

Given an array of integers, arr, remove all the even integers from the array.

Constraints:

  • 1≤1 \leq arr.length ≤103\leq 10^3
  • −105≤-10^5 \leq arr[i] ≤105\leq 10^5

Solution

The naive approach is to traverse the array and add all the odd integers to a separate array. This results in a new array, with all the even integers removed.

Here are the steps of this solution:

  1. Find the number of odd integers in the array, m.

  2. Initialize a new array, odds with size m.

  3. Traverse through arr, and for each element in the array:

    1. Append the current element to the odds array if it’s an odd integer (i.e., not divisible by 2).

  4. Finally, return odds after all elements of arr are traversed.

Let’s look at the illustration below to better understand the solution:

canvasAnimation-image
1 / 10

Let’s look at the code for this solution below:

C++ 17
#include <iostream>
#include <string>
#include <cmath>
int* removeEven(int* arr, int &size) {
    int m = 0;
    //Find number of odd elements in arr
    for (int i = 0; i < size; i++) {
        if (arr[i] % 2 != 0) {
            ++m;
        }
    }
    //Create odds array with the size equal to the number of odd elements in arr
    int* odds = new int[m];
    int n = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] % 2 != 0) { // Check if the item in the array is not even
            odds[n++] = arr[i]; // If it isn't even, append it to the odds array
        }
    }
    size = m; 
    return odds; 
}
int main() {
    int inputs[][10] = {{3, 2, 41, 3, 34}, 
                       {-5, -4, -3, -2, -1},
                       {-1, 2, 3, -4, -10},
                       {1, 2, 3, 7},
                       {2, 4, 6, 8, 10}};
    
    int sizes[] = {4, 5, 5, 1, 5}; 
    int* result;
    for (int i = 0; i < sizeof(inputs)/sizeof(inputs[0]); ++i) {
        std::cout << i + 1 << ".\tArray: [";
        for (int j = 0; j < sizes[i]; ++j) {
            if(j==sizes[i]-1)
                std::cout << inputs[i][j];
            else
                std::cout << inputs[i][j] << ", ";
        }
        std::cout <<"]"<< std::endl;
        
        result = removeEven(inputs[i], sizes[i]);
        
        std::cout << "\n\tResult: [";
        for (int j = 0; j < sizes[i]; ++j) {
            if(j==sizes[i]-1)
                std::cout << result[j];
            else
                std::cout << result[j] << ", ";
        }
        std::cout <<"]"<< std::endl;
        
        
        delete[] result;
        
        std::cout << std::string(100, '-') << std::endl;
    }
    
    return 0;
}

Complexity analysis

Let’s look at the time and space complexity of this solution:

Time complexity

The time complexity of the solution is O(n)O(n) because the input array is traversed once, where nn is the number of elements in the array.

Space complexity

The space complexity is O(1)O(1) because no extra space is used.