remove duplicates and shift to left

[newGrl]

Hello, I'm working on a program for school and I'm a bit stuck. I read through a bunch of similar posts and couldn't find the answer. I'm not sure what I'm doing wrong.

I am trying to get the remove function to work. I have an ordered int array. I have a number n that is passed to the function. Each time the function is called, the program is supposed to look for duplicates of n and remove them from the array, shifting everything to the left, and decrementing the size of the array. As far as I can tell, my code looks just like the examples I've seen online, but it's not working.

We are not allowed to change main or the function prototypes at all.

  #include <iostream>

using namespace std;
// DO NOT ALTER THE FUNCTION PROTOTYPES
void insert(int[], int &, int);
void remove(int[], int &, int);
void printArray(int [], int &); 

const int MAX = 100;

int main() {

  // DO NOT ALTER main() AT ALL!

  int nums[MAX] = {0};
  int size = 0;

  insert (nums, size, 1);
  printArray(nums, size);
  insert (nums, size, 1);
  printArray(nums, size);
  insert (nums, size, 5);
  printArray(nums, size);
  insert (nums, size, 4);
  printArray(nums, size);
  insert (nums, size, 5);
  printArray(nums, size);

  remove (nums, size, 4);
  printArray(nums, size);
  remove (nums, size, 7);
  printArray(nums, size);
  remove (nums, size, 1);
  printArray(nums, size);
  remove (nums, size, 5);
  printArray(nums, size);

  return 0;

}

void printArray(int nums[], int &size) 
{
    cout << "[ ";
    for (int i = 0; i < size; i++) 
    {
      cout << nums[i];
      if (i != size - 1)
      cout << ", ";
    }
    cout << " ]" << endl;
}

void insert(int nums[], int &size, int n) 
{
    int temp = 0;

    nums[size] = n;

    if (nums[size-1] > nums[size])
    {
      temp = nums[size];
      nums[size] = nums[size-1];
      nums[size-1] = temp;
    }
      size++;     
}

void remove(int nums[], int &size, int n) 
{
  int i, j, k;
  
  nums[i] = n;

  for(i=0;i<size-1;i++)
    for(j=i+1;j<size-1;j++)
    {
      if(nums[i]==nums[j])
      {
	for(k=j;k<size-1;k++)
          nums[k]=nums[k+1];
          size--;
			}
	}
}

Here's the output I'm getting:

[ 1 ]
[ 1, 1 ]
[ 1, 1, 5 ]
[ 1, 1, 4, 5 ]
[ 1, 1, 4, 5, 5 ]
[ 4, 1, 5, 5 ]
[ 4, 1, 5, 7 ]
[ 4, 1, 5, 1 ]
[ 4, 1, 5, 5 ]

This is what the output should look like:

[ 1 ]
[ 1, 1 ]
[ 1, 1, 5 ]
[ 1, 1, 4, 5 ]
[ 1, 1, 4, 5, 5 ]
[ 1, 1, 5, 5 ]
7 is not in the array!
[ 1, 1, 5, 5 ]
[ 5, 5 ]
[ ]

Thanks in advance for any help!

[Ganado]

Your issue appears to be when you first remove a number, right?
So isolate that from the rest of your program, and test it.

Yes, I know you're not allowed to edit main, but you can still do it on your side just for testing purposes. Revert it back afterwards.

e.g.

int main()
{
  int nums[100] = { 1, 1, 4, 5, 5 };
  int size = 5;

  remove (nums, size, 4);
  printArray(nums, size);
  
  return 0;
}

Now, you have isolated the issue to just one function call.

However, there's a more obvious issue. Please turn on compiler warnings! It will save you future headaches! On GCC/clang, use at least -Wall. On Visual Studio, see: https://www.learncpp.com/cpp-tutorial/configuring-your-compiler-warning-and-error-levels/

 In function 'void remove(int*, int&, int)':
73:9: warning: 'i' is used uninitialized in this function [-Wuninitialized]
 

Your program has undefined behavior. You never initialized i to a proper value.

[dhayden]

Based on the output, it appears that the array is supposed to be sorted. So insert() is supposed to insert the item in the right location. Is that true? Your insert() method works for the input given but not for the general case. For example, if you tried to insert 2, I don't think it would put it in the right place.

As for the remove() method, I always find it easier to do it like this:

- Create two variables, src and dst. Src will walk through the array. It is your "source" item.
dst is the "destination" item. You copy items from src to dst as you go.
- When you're done, adjust the size of the array. Keep in mind that you might have removed
multiple items.

You do the work with one pass through the array, at each iteration, you either skip the src item or you copy it to dst and increment the dst pointer.

[keskiverto]

One could cheat^H^H^H use the "easy way" and implement the remove with std::remove.
However, that probably won't get due appreciation ... and provides a different challenge.

The documentation page about std::remove http://www.cplusplus.com/reference/algorithm/remove/
does show a code example that essentially does what dhayden did describe.
To understand and adapt form that is again a different challenge.

Note though that "remove X" and "remove duplicates of X" are different operations.
The first removes all occurrences of value X.
The second removes all but one X.

If we are told to remove X (or duplicates of it), then sorted/unsorted could be a non-issue.
If we are expected to maintain ordering during insert, then insert must enforce that invariable.