Remove duplicates from array C++

Input: int arr[] = {10, 20, 20, 30, 40, 40, 40, 50, 50}

Output: 10, 30

My code:

int removeDup(int arr[], int n)
{
    int temp;
    bool dupFound = false;

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(arr[i] == arr[j]){
                if(!dupFound){
                    temp = arr[i];
                    dupFound = true;
                }
                else{
                    arr[i] = temp;
                }
            }
        }
    }
    //shift here
}

First of all, I don’t know if this is the most efficient way of doing this.

I’m trying to find the first duplicate element, assign it to every duplicate element and shift them to the end of the array, which doesn’t work because the last duplicate element cannot be compared.

I need some help with finding the last duplicate element, so I can assign temp to it.

>Solution :

Instead of trying to do everything at once, let us focus on correctness first:

int removeDup(int* arr, int n) {
  // Note: No i++! This depends on whether we find a duplicate.
  for (int i = 0; i < n;) {
    int v = arr[i];
    bool dupFound = false;

    for (int j = i+1; j < n; j++) {
      if (v == arr[j]) {
        dupFound = true;
        break;
      }
    }

    if (!dupFound) {
      i++;
      continue;
    }

    // Copy values to the sub-array starting at position i,
    // skipping all values equal to v. 
    int write = i, skipped = 0;
    for (int j = i; j < n; j++) {
      if (arr[j] != v) {
        arr[write] = arr[j];
        write++;
      } else {
        skipped++;
      }
    }

    // The previous loop duplicated some non-v elements.
    // We decrease n to make sure these duplicates are not
    // considered in the output
    n -= skipped;
  }

  return n;
}