## Tuesday, May 24, 2016

### Absolute distinct count in a sorted array - GeeksforGeeks

Absolute distinct count in a sorted array - GeeksforGeeks
Given a sorted array of integers, return the number of distinct absolute values among the elements of the array. The input can contain duplicates values.
```Input: [-3, -2, 0, 3, 4, 5]
Output: 5
There are 5 distinct absolute values
among the elements of this array, i.e.
0, 2, 3, 4 and 5)
```

```
The solution should do only one scan of the input array and should not use any extra space. i.e. expected time complexity is O(n) and auxiliary space is O(1).

The idea is to take advantage of the fact that the array is already Sorted. We initialize the count of distinct elements to number of elements in the array. We start with two index variables from two corners of the array and check for pair in the input array with sum as 0. If pair with 0 sum is found or duplicates are encountered, we decrement the count of distinct elements.Finally we return the updated count.

`int` `distinctCount(``int` `arr[], ``int` `n)`

`{`

`    ``// initialize count as number of elements`

`    ``int` `count = n;`

`    ``int` `i = 0, j = n - 1, sum = 0;`

`    ``while` `(i < j)`

`    ``{`

`        ``// Remove duplicate elements from the`

`        ``// left of the current window (i, j)`

`        ``// and also decrease the count`

`        ``while` `(i != j && arr[i] == arr[i + 1])`

`            ``count--, i++;`

`        ``// Remove duplicate elements from the`

`        ``// right of the current window (i, j)`

`        ``// and also decrease the count`

`        ``while` `(i != j && arr[j] == arr[j - 1])`

`            ``count--, j--;`

`        ``// break if only one element is left`

`        ``if` `(i == j)`

`            ``break``;`

`        ``// Now look for the zero sum pair`

`        ``// in current window (i, j)`

`        ``sum = arr[i] + arr[j];`

`        ``if` `(sum == 0)`

`        ``{`

`            ``// decrease the count if (positive,`

`            ``// negative) pair is encountered`

`            ``count--;`

`            ``i++, j--;`

`        ``}`

`        ``else` `if``(sum < 0)`

`            ``i++;`

`        ``else`

`            ``j--;`

`    ``}`

`    ``return` `count;`

`}`

```