Given a sorted array arr[] of size N, the task is to find the number of unique elements in this array.
Note: The array is very large, and unique numbers are significantly less. i.e., (unique elements <<size of the array).
Examples:
Input: arr[] = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12}
Output: 10
Explanation: 10 unique elements are: 1, 2, 3, 5, 7, 8, 9, 10, 11, 12Input: arr[] = {1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 9, 9, 9, 10, 10, 10}
Output: 7
Explanation: 7 unique elements are: 1, 2, 3, 4, 5, 9, 10
Naive Approach: As the given array is sorted, one of the simple approaches will be traversing through all over the element and comparing them with the previous ones. If it is different, then count that element.
Time Complexity: O(N)
Auxiliary Space: O(1).
Approach based on Binary Search: The idea is the use Binary search because the array is sorted. Follow the steps mentioned below:
- Take the first number, then find its last occurrence or upper bound using binary search.
- Then count it as one unique element.
- Place pointer to next different element and repeat the same step.
Note: This algorithm is only effective when very few unique elements.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Binary search to find the last occurrenceint nextIndex(int arr[], int N, int l, int target){ int result = -1; int r = N - 1; while (l <= r) { int mid = l + (r - l) / 2; if (arr[mid] == target) { result = mid; l = mid + 1; } else if (arr[mid] > target) r = mid - 1; else l = mid + 1; } // Result will give the last occurrence & // adding one will return next element return result + 1;}// Function to find the number// of unique elementsint unique(int arr[], int N){ int i = 0; int count = 0; while (i < N) { // Returns the next element i = nextIndex(arr, N, i, arr[i]); count++; } return count;}// Driver Codeint main(){ int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }; int N = sizeof(arr) / sizeof(arr[0]); cout << unique(arr, N); return 0;} |
Java
// Java code to implement above approachclass GFG { // Binary search to find the last occurrence static int nextIndex(int arr[], int N, int l, int target) { int result = -1; int r = N - 1; while (l <= r) { int mid = l + (r - l) / 2; if (arr[mid] == target) { result = mid; l = mid + 1; } else if (arr[mid] > target) r = mid - 1; else l = mid + 1; } // Result will give the last occurrence & // adding one will return next element return result + 1; } // Function to find the number // of unique elements static int unique(int arr[], int N) { int i = 0; int count = 0; while (i < N) { // Returns the next element i = nextIndex(arr, N, i, arr[i]); count++; } return count; } // Driver Code public static void main(String args[]) { int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }; int N = arr.length; System.out.println(unique(arr, N)); }} |
Python3
# Python code for the above approach# Binary search to find the last occurrencedef nextIndex(arr, N, l, target): result = -1 r = N - 1 while (l <= r): mid = l + (r - l) // 2 if (arr[mid] == target): result = mid l = mid + 1 elif (arr[mid] > target): r = mid - 1 else: l = mid + 1 # Result will give the last occurrence & # adding one will return next element return result + 1# Function to find the number# of unique elementsdef unique(arr, N): i = 0 count = 0 while (i < N): # Returns the next element i = nextIndex(arr, N, i, arr[i]) count += 1 return count# Driver Codearr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12]N = len(arr)print(unique(arr, N))# This code is contributed by gfgking |
C#
// C# program for above approachusing System;using System.Collections.Generic;public class GFG{ // Binary search to find the last occurrence static int nextIndex(int[] arr, int N, int l, int target) { int result = -1; int r = N - 1; while (l <= r) { int mid = l + (r - l) / 2; if (arr[mid] == target) { result = mid; l = mid + 1; } else if (arr[mid] > target) r = mid - 1; else l = mid + 1; } // Result will give the last occurrence & // adding one will return next element return result + 1; } // Function to find the number // of unique elements static int unique(int[] arr, int N) { int i = 0; int count = 0; while (i < N) { // Returns the next element i = nextIndex(arr, N, i, arr[i]); count++; } return count; } // Driver Code static public void Main (){ int[] arr = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }; int N = arr.Length; Console.WriteLine(unique(arr, N)); }}// This code is contributed by hrithikgarg03188 |
Javascript
<script> // JavaScript code for the above approach // Binary search to find the last occurrence function nextIndex(arr, N, l, target) { let result = -1; let r = N - 1; while (l <= r) { let mid = l + Math.floor((r - l) / 2); if (arr[mid] == target) { result = mid; l = mid + 1; } else if (arr[mid] > target) r = mid - 1; else l = mid + 1; } // Result will give the last occurrence & // adding one will return next element return result + 1; } // Function to find the number // of unique elements function unique(arr, N) { let i = 0; let count = 0; while (i < N) { // Returns the next element i = nextIndex(arr, N, i, arr[i]); count++; } return count; } // Driver Code let arr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12]; let N = arr.length; document.write(unique(arr, N)); // This code is contributed by Potta Lokesh </script> |
Output
10
Time Complexity: K * logO(N). where K = no. of unique elements.
Auxiliary Space: O(1).
Approach based on Divide and Conquer: This problem can be solved using divide and conquer. Idea is:
- As duplicate elements are large, look at the first and last elements of this sorted array.
- If both are equal, it means only this element is present in the entire array, and it will be counted as one.
- If they are different, divide the array into two halves and repeat the above step for each array.
- The final count is the number of unique elements.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Variable to store the number// of unique elementsint cnt = 0;// Function to find the number// of unique elementsvoid UniqueElements(int arr[], int s, int e, bool isDuplicate){ // Both start and end are same if (arr[s] == arr[e]) { // If the element is duplicate if (isDuplicate == false) { cnt++; } } else { int mid = s + (e - s) / 2; UniqueElements(arr, s, mid, isDuplicate); UniqueElements(arr, mid + 1, e, arr[mid] == arr[mid + 1]); }}// Function to count the number// of unique elementsint unique(int arr[], int N){ UniqueElements(arr, 0, N - 1, 0); return cnt;}// Driver Codeint main(){ int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }; int N = sizeof(arr) / sizeof(arr[0]); cout << unique(arr, N); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG{ // Variable to store the number // of unique elements static int cnt = 0; // Function to find the number // of unique elements static void UniqueElements(int arr[], int s, int e, boolean isDuplicate) { // Both start and end are same if (arr[s] == arr[e]) { // If the element is duplicate if (isDuplicate == false) { cnt++; } } else { int mid = s + (e - s) / 2; UniqueElements(arr, s, mid, isDuplicate); UniqueElements(arr, mid + 1, e, arr[mid] == arr[mid + 1]); } } // Function to count the number // of unique elements static int unique(int arr[], int N) { UniqueElements(arr, 0, N - 1, false); return cnt; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }; int N = arr.length; System.out.print(unique(arr, N)); }}// This code is contributed by 29AjayKumar |
Python3
# Python code to implement the above approach# Variable to store the number# of unique elementscnt = 0;# Function to find the number# of unique elementsdef UniqueElements(arr, s, e, isDuplicate): global cnt # Both start and end are same if (arr[s] == arr[e]): # If the element is duplicate if (isDuplicate == False): cnt += 1; else: mid = s + (e - s) // 2; UniqueElements(arr, s, mid, isDuplicate); UniqueElements(arr, mid + 1, e, arr[mid] == arr[mid + 1]); # Function to count the number# of unique elementsdef unique(arr, N): UniqueElements(arr, 0, N - 1, False); return cnt;# Driver Codeif __name__ == '__main__': arr = [ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 ]; N = len(arr); print(unique(arr, N));# This code is contributed by Rajput-Ji |
C#
// C# code to implement the above approachusing System;public class GFG{ // Variable to store the number // of unique elements static int cnt = 0; // Function to find the number // of unique elements static void UniqueElements(int []arr, int s, int e, bool isDuplicate) { // Both start and end are same if (arr[s] == arr[e]) { // If the element is duplicate if (isDuplicate == false) { cnt++; } } else { int mid = s + (e - s) / 2; UniqueElements(arr, s, mid, isDuplicate); UniqueElements(arr, mid + 1, e, arr[mid] == arr[mid + 1]); } } // Function to count the number // of unique elements static int unique(int []arr, int N) { UniqueElements(arr, 0, N - 1, false); return cnt; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }; int N = arr.Length; Console.Write(unique(arr, N)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// javascript code to implement the above approach // Variable to store the number // of unique elements var cnt = 0; // Function to find the number // of unique elements function UniqueElements(arr , s,e, isDuplicate) { // Both start and end are same if (arr[s] == arr[e]) { // If the element is duplicate if (isDuplicate == false) { cnt++; } } else { var mid = s + parseInt((e - s) / 2); UniqueElements(arr, s, mid, isDuplicate); UniqueElements(arr, mid + 1, e, arr[mid] == arr[mid + 1]); } } // Function to count the number // of unique elements function unique(arr , N) { UniqueElements(arr, 0, N - 1, false); return cnt; } // Driver Code var arr = [ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 ]; var N = arr.length; document.write(unique(arr, N));// This code is contributed by shikhasingrajput </script> |
Output
10
Time Complexity: O(log(N)) for the average case.The worst case will be O(N).
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
