Count distinct absolute values in a sorted array

Posted in

Count distinct absolute values in a sorted array
maazbinasad

Maaz Bin Asad
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]

    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:

    Leave a Comment on this Post

    0 Comments