Arrays: Given a sorted array return the absolute distinct count.

Problem Statement:

You are given an sorted array with duplicates and -ve values.

You need to return the absolute values of distinct values.

Example:

Input: [-3, -2, -1, 0, 3, 3, 4, 5]

Output: 6

Explanation:

There are 6 distinct elements [3, 2, 1, 0, 4, 5]

Input:  [-2, -2, -2, -2, 0]
Output: 2

Input:  [1, 1, 1]
Output: 1 

Solution Explanation:

The solution is very simple, we need to find out the absolute distinct elements count.

It means we need to convert all the -ve values into +ve values.

So the first example array will become: [3, 2, 1, 0, 3, 3, 4, 5]

Now we will calculate the distinct count, meaning the number of unique elements is 6.

To solve the problem, we will use Set DS.

Set DS will not accept duplicate values and we can insert absolute values.

Then we take the size of the set will give the result.

Time Complexity : O(n)
Auxiliary Space : O(n)

Code Solution

#include<iostream>
#include<set>
#include<cmath>

using namespace std;

int solution(int arr[], int n)
{
    set<int> s;

    for(int i = 0; i<n; i++)
    {
        s.insert(abs(arr[i])); 
    }
    return s.size();
}

int main() 
{
    int arr[] = {-3, -2, -1, 0, 3, 3, 4, 5};
    int n = (sizeof(arr))/(sizeof(arr[0]));
    cout << "Absolute Distinct Count: " << solution(arr, n);
    return 0;
}

Output

Absolute Distinct Count: 6