Count distinct absolute values in a sorted array

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]

Sample Output

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;
}

Output

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));

Output

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));
 
 
 }
}

Output

3

People are also reading:

• Merge Two Sorted Arrays in-place
• Longest subarray with sum as K
• Rod Cutting Problem – Dynamic Programming
• Maximum of all Subarrays of size K
• Sort binary array in linear time
• Move all zeros present in an array to the end
• Subarray with Sum k
• Find Maximum Subarray Sum
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Dutch National Flag Problem