Remove Even Integers From an Array - MyTechiest

It is a simple array-based based problem in which you need to remove all the even elements from the given array.

Sample Input 

Arr = [1,2,4,5,10,6,3]

Sample Output 

Arr = [1,5,3]

Output

int * removeEven( int *& Arr, int size )
{
    int m = 0;
    for (int i = 0; i < size; i++)
    {
        if ( Arr[i] % 2 != 0 )  // if odd number found
        {
            if ( i != m ) {
              Arr[m] = Arr[i];   //inserting odd values in array
            }
            ++m;
        }
    }
  	int * temp = new int[m];
  	for(int i = 0; i< m; i++)
      temp[i] = Arr[i];
  
    delete [] Arr;
  	Arr = temp;
    return Arr;  // returning array after removing odd numbers
}

int main(){
  int * arr;      // declaring array
  arr = new int[10];   // memory allocation
  cout << "Before remove even: "; 
  for ( int i = 0; i < 10; i++ )
  {
    arr[i] = i;      // assigning values
    cout << arr[i] << " ";
  }
  cout << endl;
  arr = removeEven(arr,10);   // calling removeEven
  cout << "After remove even: ";
  for ( int i = 0; i < 5; i++ )
  {
    cout << arr[i] << " ";    // prinitng array
  }
  delete [] arr;  // deleting allocated memory
  return 0;
}

Explanation

This solution starts with the first element of an Array, checks if it is odd, then appends this element to the start of an array. Otherwise, it jumps to the next element. This repeats until the end of an array is reached by keeping the count of total odd numbers m in an array. Now, make a temporary array to store all odd numbers in it. Delete the memory allocated to Arr and point it to the temp array and return the Arr containing odd elements only.

Time Complexity

Since the entire array has to be iterated over, this solution works in $O(n)$.