# Count distinct absolute values in a sorted array

Posted in

Last updated on February 21, 2024

## Problem

Given a sorted array of integers, return the number of distinct absolute values among the elements of the array.

#### Sample Input

`[-1, 0, 1, 2]`

`3`

### Approach 1

We can simply insert absolute values of integers in a set and return the size of the set. This takes O(N) time and O(N) extra space.

### Approach 2

Since the array is sorted, we initialize the count of our answer to the total number of elements in the array. We start with the two ends of the array and check for pairs in the input array with a sum of 0. If a pair with 0 sum is encountered, we decrement the count of distinct elements. This approach takes O(N) time and O(1) extra space.

#### C++

```#include <bits/stdc++.h>
using namespace std;
intsolve(int arr[], int n)
{
int ans = n;
int i = 0, j = n - 1, sum = 0;
while (i < j)
{
while (i != j && arr[i] == arr[i + 1])
ans--, i++;
while (i != j && arr[j] == arr[j - 1])
ans--, j--;
if (i == j)
break;
sum = arr[i] + arr[j];
if (sum == 0)
{
ans--;
i++, j--;
}
elseif(sum < 0)
i++;
else
j--;
}
return ans;
}
intmain()
{
int arr[] = {-1, 0, 1, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout <<solve(arr, n);
return0;
}
```

`3`

#### Python

```def solve(arr, n):
ans = n;
i = 0; j = n - 1; sum = 0;
while (i < j):

while (i != j and arr[i] == arr[i + 1]):
ans = ans - 1;
i = i + 1;
while (i != j and arr[j] == arr[j - 1]):
ans = ans - 1;
j = j - 1;
if (i == j):
break;
sum = arr[i] + arr[j];
if (sum == 0):

ans = ans - 1;
i = i + 1;
j = j - 1;

elif(sum < 0):
i = i + 1;
else:
j = j - 1;

return ans;
arr = [-1, 0, 1, 2];
n = len(arr);
print(solve(arr, n));```

`3`

#### Java

```import java.io.*;
classSolution {

staticintsolve(int arr[], int n)
{
int ans = n;
int i = 0, j = n - 1, sum = 0;
while (i < j)
{
while (i != j && arr[i] == arr[i + 1])
{
ans--;
i++;
}
while (i != j && arr[j] == arr[j - 1])
{
ans--;
j--;
}

if (i == j)
break;
sum = arr[i] + arr[j];
if (sum == 0)
{
ans--;
i++;
j--;
}
elseif(sum < 0)
i++;
else
j--;
}
return ans;
}

publicstaticvoidmain (String[] args) {

int arr[] = {-1, 0, 1, 2};
int n = arr.length;
System.out.println (solve(arr, n));

}
}```

`3`