Remove all occurrences of a number in an array in C++

[claudilla]

Supposed we passed in the array {1, 2, 3, 1, 2, 3, 1}, and we wanted to remove all occurrences of the number 3. The resulting array would be {1, 2, 1, 2, 1}, and the return value would be 5, because there are now only 5 items in the array. This function is wrong. I don't know how to remove the occurrences. I know my index holds the positions of the occurrences. So i need to delete those positions from my array. HELP!! I can only use arrays, i cannot use vectors or pointers.
Here is my updated code.

void test() {

	int data[] = { 2, 1, 3, 2, 5, 2, 7, 8, 4, 9 };
	int length = 10;
	int x = 2;
	int index = 0;
	int counter =0;


	int tempIndex = 0;
	int finalLength = 0;
	for (int i = 0; i < length; i++)
	{
		if (x != data[i]) {

			tempIndex = i;
			counter++;
			cout << "Array: " << tempIndex << endl;
		}
	}
	cout << "Size: " << counter << endl;

	
}
}

[Duthomhas]

There are actually two things going on here:

1. You must find the index of a 3 in the array
2. You must remove the 3 from the array

Finding the 3 is easy:

  2 1 3 2 5 2 7 8 4 9
  ^ nope
  2 1 3 2 5 2 7 8 4 9
    ^ nope
  2 1 3 2 5 2 7 8 4 9
       ^ found a 3 at index 2

Now you need to get rid of the three. One way to do it is to simply shift the contents of the array one item to the left, starting at the index you found.

  2 1 3 2 5 2 7 8 4 9
  2 1 2 5 2 7 8 4 9

This is the trick you need to solve. Move everything from (3+1)..(end) → (3)..(end-1).
I highly recommend writing a function to do it for you. That way you can concentrate on one thing at a time. Here is a prototype to help:

  void shift( int xs[], int from, int to, int n ); 

So, to move everything starting at position 4 to start at position 3, you could say:

  shift( data, index+1, index, length-index-1 );
  length -= 1;

See how that works? Worry about one thing at a time.

Good luck!

[claudilla]

I see. I tried my code and it is giving me the right output. Does that mean that my code is not right or efficient?

void test() {

	int data[] = { 2, 1, 3, 2, 5, 2, 7, 8, 4, 9 };
	int length = 10;
	int x = 2;
	int index = 0;
	int counter =0;


	int tempIndex = 0;
	int finalLength = 0;
	for (int i = 0; i < length; i++)
	{
		if (x != data[i]) {

			tempIndex = i;
			counter++;
			cout << "Array: " << tempIndex << endl;
		}
	}
	cout << "Size: " << counter << endl;

	
}
}

[JLBorges]

> Does that mean that my code is not right or efficient?

You make just one single pass from through the array: that is the minimum required.

In your code, you are printing out what the array would look like if the elements were removed;
to actually implement the remove, the non-removed elements in the array must be moved to the left.

This can be made a bit more efficient by avoiding the redundant moves of elements which are before the first occurrence of the value that is to be removed.

For instance:

#include <iostream>

// remove all occurrences of value in the array of logical size n.
// return the new logical size of the array after removal
// complexity: exactly one pass through the array
std::size_t remove( int* array, std::size_t n, int value ) {

    // get to the first occurrence of value
    // (we don't need to move anything before this)
    std::size_t pos = 0 ;
    for( ; pos < n && array[pos] != value ; ++pos ) ;
    if( pos == n ) return n ; // not found; there is nothing to remove

    // now, make one pass from pos+1 up to the end of the array,
    // moving the non-removed elements to the left

    // the target position of the next element which is not removed
    std::size_t move_to = pos ;

    for( std::size_t i = pos ; i++ < n ; ) // from pos+1 up to the end of the array
        if( array[i] != value ) array[move_to++] = array[i] ;

    return move_to-1 ; // return the new logical end of the array
}

int main() {

    int a[] { 2, 1, 3, 2, 5, 2, 7, 8, 4, 9, 2, 4, 3, 7, 6 } ;
    auto sz = sizeof(a) / sizeof(*a) ;

    std::cout << "original array: [ " ;
    for( std::size_t i = 0 ; i < sz ; ++i ) std::cout << a[i] << ' ' ;
    std::cout << "]  size: " << sz << '\n' ;

    for( int v : { 6, 2, 7, 1, 9, 4, 0 } ) {

        sz = remove( a, sz, v ) ;

        std::cout << "after remove " << v << ": [ " ;
        for( std::size_t i = 0 ; i < sz ; ++i ) std::cout << a[i] << ' ' ;
        std::cout << "]  size: " << sz << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/11166bc12cf82340