Find unique element in sorted array using c++

Question

I am trying to find unique element from the array these is question

Input  : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
Output : arr[] = {1, 2, 3, 4, 5}

They give me correct output but why they give 0 at the end in output:

these is my output:
{1,2,3,4,5,0}

Code:

#include<iostream>
using namespace std;
int main(){
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int n=sizeof(arr)/sizeof(arr[0]);
    int c=0;
    for(int j=0;j<=n;j++){
        if(arr[j]!=arr[j+1]){
            cout<<arr[j];
            }


    }
   
}

Have you tried [`std::unique`?](https://en.cppreference.com/w/cpp/algorithm/unique) — Thomas Matthews, Sep 06 '22 at 20:18
Your code invokes undefined behavior. `n` is the count of elements. Your loop caps on exceeding `n` (problem #1) and even if fixed you also index `j+1`. Both are wrong. Each causes a breach of your array; doing both just pours extra salt on the wound. — WhozCraig, Sep 06 '22 at 20:20
OT: don't use `sizeof` to determine the size of an array. Its too easy to use it wrong. Use `std::size` instead. In cases where `sizeof(x)/sizeof(x[0])` produces meansingless results `std::size` fails to compile — 463035818_is_not_an_ai, Sep 06 '22 at 20:26
What you're probably shooting for is more along the lines of: output the first element (which will always be included). From there, loop on `j=1; j — WhozCraig, Sep 06 '22 at 20:32
@developer FYI -- [See std::unique and std::set](https://godbolt.org/z/1eaKrY3ha) — PaulMcKenzie, Sep 06 '22 at 20:48

score 0 · Answer 1 · edited Sep 11 '22 at 15:51

0

problem is in for loop becouse you use less or equal to n. you need to use just less then n becouse array starts from zero that means you asking for sixth element that do not have alocalizated in memory

now it should be correct

#include<iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int n=sizeof(arr)/sizeof(arr[0]);
    int c=0;
    for(int j=0; j<n; j++) {
        if (arr[j]!=arr[j+1]) {
            cout<<arr[j];
        }
    }
}

edited Sep 11 '22 at 15:51

Tyler2P

2,324
26
22
31

answered Sep 06 '22 at 20:40

Aleš Prášek

1

In general when you see `<=` in the exit condition of a loop iterating a container, you're probably looking at an off-by-one bug. It's always worth stopping and inspecting the code more closely to make sure it is correct. – user4581301 Sep 06 '22 at 20:43
2

On the last iteration of your loop `arr[j+1]` reads past the end of the array. – Blastfurnace Sep 06 '22 at 20:44
1

Side note: as of C++17 use [`std::size`](https://en.cppreference.com/w/cpp/iterator/size) in place of `int n=sizeof(arr)/sizeof(arr[0]);`. It is simpler and will make common misuses brutally obvious by failing to compile. Before C++17 consider writing your own. [See the fourth possible implementation here](https://en.cppreference.com/w/cpp/iterator/size#Possible_implementation). – user4581301 Sep 06 '22 at 20:46

score 0 · Accepted Answer · answered Sep 06 '22 at 21:14

Except for std::cout, you code is much more C than ++.

std::unique of the C++ Standard Library does exactly what you want. There is no need to re-implement this.
Next there is the erase-remove idiom to delete the superfluous elements.
For the output, you can use std::for_each() or at least a range-based for loop.
And also, you don't want using namespace std;

A more modern solution looks like this:

#include <iostream>
#include <algorithm>
#include <vector>
int main(){
    std::vector<int> arr {1, 2, 2, 3, 4, 4, 4, 5, 5};
    auto last = std::unique(arr.begin(), arr.end());
    arr.erase(last, arr.end());
    std::for_each(arr.begin(), arr.end(), [](int n){std::cout << n << std::endl;} );
}

Try it on Godbolt.

Find unique element in sorted array using c++

2 Answers2