find the element that appears once in the array when others appear twice

Question

I wrote the code with o(n^2) complexity.I could not find the error.My idea was to first sort the array and then starting from the first element if the second next is equal increment i by 2 and when the if condition is not fulfilled the element is found Can someone please help me this. Thanks in advance

#include<iostream>
using namespace std;

int main()
{
int arr[100];
int n,i,j,temp;
cin>>n;
for(i=0;i<n;i++)
{
    cin>>arr[i];
}
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        if(arr[i]>arr[j])
        {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
}
i=0;
for(j=i+1;j<n;j++)
{
    if(arr[i] == arr[j])
    {
        i=i+2;
    }
}
cout<<arr[i];
return 0;
}

Answer 1

To find a non-repetitive element in an array the first thing that comes to mind is that if we first sort the array and then try to manipulate it. The sorting process is easy and as follows:

    int arr[] = {/*Some array*/};
    int arrSize = sizeof(arr)/sizeof(int);
    //Lets sort the array
    for(int i=0;i<arrSize;i++)
    {
        for(int j=i;j<arrSize;j++)
        {
            if(arr[i]>arr[j])
            {
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
    }

After sorting the array we may see different scenarios like:

int arr1[] = {1,1,2,2,3};
int arr2[] = {1,2,2,3,3};
int arr3[] = {1,1,2,3,3};

We have to design an algorithm such that it can differentiate and easily manipulate the three scenarios. Let n be our number. The first scenario is to check if the last isn't the same as the previous one by:

    if(arr[arrSize-1] != arr[arrSize-2]) //The last is not the same as the previous
    {
        n=arr[arrSize-1];
    }

The second one is similar to the first:

    if(arr[0] != arr[1]) // The first element is not the same as the second
    {
        n = arr[0];
    }

The third one is easy too, we just have to check if two neighbors are never equal to the middle number, this is as follows:

        for(int i=1;i<arrSize-1;i++)
        {
            if(arr[i-1] != arr[i] && arr[i] != arr[i+1])
            {
                n=arr[i];
                break;
            }
        }

And so the full code would become:

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {1,2,3,4,2,3,1};
    int arrSize = sizeof(arr)/sizeof(int);
    //Lets sort the array
    for(int i=0;i<arrSize;i++)
    {
        for(int j=i;j<arrSize;j++)
        {
            if(arr[i]>arr[j])
            {
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
    }
    int n;
    if(arr[0] != arr[1]) // The first element is not the same as the second
    {
        n = arr[0];
    }
    else if(arr[arrSize-1] != arr[arrSize-2]) //The last is not the same as the previous
    {
        n=arr[arrSize-1];
    }
    else //Lets search for a number such that its not the same as the numbers on the left and on the right
    {
        for(int i=1;i<arrSize-1;i++)
        {
            if(arr[i-1] != arr[i] && arr[i] != arr[i+1])
            {
                n=arr[i];
                break;
            }
        }
    }
    cout << n;
}

The Second Way (Better one).

Here's another way we could solve this problem. Suppose that I have a number n=3, if i XORed it with 3 i will get 0, so if we have an array lets say arr[] = {1,2,1}, I first assign n=0, then XOR it with the firs element (1), next I XOR n with the second element and then with the third element. What will happen? The third XOR will cancel the effect of the first thus n will equal to 1. Sample Code:

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {1,2,3,4,2,3,1};
    int arrSize = sizeof(arr)/sizeof(int);
    int n=0;
    for(int i=0;i<arrSize;i++)
    {
        n^=arr[i];
    }
    cout << n;
}

This code is O(n).

Answer 2

Use XOR. XOR of all array elements gives us the number with a single occurrence.

#include <bits/stdc++.h>
using namespace std;
int singleoccurence(int arr[], int n)
{
    int res = arr[0];
    for (int i = 1; i < n; i++)
    {
        res = res ^ arr[i];
    }

    return res;
}
int main()
{
    int arr[] = {7, 3, 5, 4, 5, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int val = singleoccurence(arr, n);
    cout << "ELEMENT OCCURING ONLY ONCE IS :" << val;
}

Answer 3

Solution in C#

public static int lonelyinteger(List<int> a)
{
    int lonely = 0;
    foreach(var item in a)
    {
        List<int> listTemp = a.Where(x => x == item).ToList();
        if(listTemp.Count == 1)
            lonely = listTemp.FirstOrDefault();
    }
    return lonely;
}