Given two integers L and R and an array arr[] consisting of N positive integers( 1-based indexing ) such that the frequency of ith element of a sorted sequence, say A[], is arr[i]. The task is to find the number of distinct elements from the range [L, R] in the sequence A[].
Examples:
Input: arr[] = {3, 6, 7, 1, 8}, L = 3, R = 7
Output: 2
Explanation: From the given frequency array, the sorted array will be {1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, ….}. Now, the number of distinct elements from the range [3, 7] is 2( = {1, 2}).Input: arr[] = {1, 2, 3, 4}, L = 3, R = 4
Output: 2
Naive Approach: The simplest approach to solve the given problem is to construct the sorted sequence from the given array arr[] using the given frequencies and then traverse the constructed array over the range [L, R] to count the number of distinct elements.
Code-
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to count the number of// distinct elements over the range// [L, R] in the sorted sequencevoid countDistinct(vector<int> arr, int L, int R){ vector<int> vec; for(int i=0;i<arr.size();i++){ int temp=arr[i]; for(int j=0;j<temp;j++){ vec.push_back(i+1); } } int curr=INT_MIN; int count=0; for(int i=L-1;i<R;i++){ if(curr!=vec[i]){ count++; curr=vec[i]; } } cout<<count<<endl;}// Driver Codeint main(){ vector<int> arr{ 3, 6, 7, 1, 8 }; int L = 3; int R = 7; countDistinct(arr, L, R);} |
Java
import java.util.*;class GFG { // Function to count the number of // distinct elements over the range // [L, R] in the sorted sequence static void countDistinct(ArrayList<Integer> arr, int L, int R) { ArrayList<Integer> vec = new ArrayList<Integer>(); for (int i = 0; i < arr.size(); i++) { int temp = arr.get(i); for (int j = 0; j < temp; j++) { vec.add(i + 1); } } int curr = Integer.MIN_VALUE; int count = 0; for (int i = L - 1; i < R; i++) { if (curr != vec.get(i)) { count++; curr = vec.get(i); } } System.out.println(count); } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>( Arrays.asList(3, 6, 7, 1, 8)); int L = 3; int R = 7; countDistinct(arr, L, R); }} |
Python3
# Python program for the above approachdef countDistinct(arr, L, R): # create a new vector vec = [] for i in range(len(arr)): temp = arr[i] for j in range(temp): vec.append(i+1) curr = float('-inf') count = 0 for i in range(L-1, R): if curr != vec[i]: count += 1 curr = vec[i] print(count)# Driver Codeif __name__ == '__main__': arr = [3, 6, 7, 1, 8] L = 3 R = 7 countDistinct(arr, L, R) |
C#
using System;using System.Collections.Generic;class GFG{ // Function to count the number of distinct elements over the range // [L, R] in the sorted sequence static void CountDistinct(List<int> arr, int L, int R) { List<int> vec = new List<int>(); // Create a sorted sequence with occurrences of elements from the input array foreach (int temp in arr) { for (int j = 0; j < temp; j++) { vec.Add(arr.IndexOf(temp) + 1); } } int curr = int.MinValue; int count = 0; // Count the number of distinct elements in the range [L, R] for (int i = L - 1; i < R; i++) { if (curr != vec[i]) { count++; curr = vec[i]; } } Console.WriteLine(count); } // Driver Code static void Main() { List<int> arr = new List<int> { 3, 6, 7, 1, 8 }; int L = 3; int R = 7; CountDistinct(arr, L, R); }} |
Javascript
// Function to count the number of// distinct elements over the range// [L, R] in the sorted sequencefunction countDistinct(arr, L, R) { // creating sorted sequence let vec = []; for (let i = 0; i < arr.length; i++) { let temp = arr[i]; for (let j = 0; j < temp; j++) { vec.push(i + 1); } } // Counting distinct elements let curr = Number.MIN_SAFE_INTEGER; let count = 0; for (let i = L - 1; i < R; i++) { if (curr !== vec[i]) { count++; curr = vec[i]; } } console.log(count);}// test caselet arr = [3, 6, 7, 1, 8];let L = 3;let R = 7;countDistinct(arr, L, R); |
Output
2
Time Complexity: O(S + R – L)
Auxiliary Space: O(S), where S is the sum of the array elements.
Efficient Approach: The above approach can be optimized by using the Binary Search and the prefix sum technique to find the number of distinct elements over the range [L, R]. Follow the steps below to solve the given problem:
- Initialize an auxiliary array, say prefix[] that stores the prefix sum of the given array elements.
- Find the prefix sum of the given array and stored it in the array prefix[].
- By using binary search, find the first index at which the value in prefix[] is at least L, say left.
- By using binary search, find the first index at which the value in prefix[] is at least R, say right.
- After completing the above steps, print the value of (right – left + 1) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the first index// with value is at least elementint binarysearch(int array[], int right, int element){ // Update the value of left int left = 1; // Update the value of right // Binary search for the element while (left <= right) { // Find the middle element int mid = (left + right / 2); if (array[mid] == element) { return mid; } // Check if the value lies // between the elements at // index mid - 1 and mid if (mid - 1 > 0 && array[mid] > element && array[mid - 1] < element) { return mid; } // Check in the right subarray else if (array[mid] < element) { // Update the value // of left left = mid + 1; } // Check in left subarray else { // Update the value of // right right = mid - 1; } } return 1;}// Function to count the number of// distinct elements over the range// [L, R] in the sorted sequencevoid countDistinct(vector<int> arr, int L, int R){ // Stores the count of distinct // elements int count = 0; // Create the prefix sum array int pref[arr.size() + 1]; for(int i = 1; i <= arr.size(); ++i) { // Update the value of count count += arr[i - 1]; // Update the value of pref[i] pref[i] = count; } // Calculating the first index // of L and R using binary search int left = binarysearch(pref, arr.size() + 1, L); int right = binarysearch(pref, arr.size() + 1, R); // Print the resultant count cout << right - left + 1;}// Driver Codeint main(){ vector<int> arr{ 3, 6, 7, 1, 8 }; int L = 3; int R = 7; countDistinct(arr, L, R);}// This code is contributed by ipg2016107 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the first index // with value is at least element static int binarysearch(int array[], int element) { // Update the value of left int left = 1; // Update the value of right int right = array.length - 1; // Binary search for the element while (left <= right) { // Find the middle element int mid = (int)(left + right / 2); if (array[mid] == element) { return mid; } // Check if the value lies // between the elements at // index mid - 1 and mid if (mid - 1 > 0 && array[mid] > element && array[mid - 1] < element) { return mid; } // Check in the right subarray else if (array[mid] < element) { // Update the value // of left left = mid + 1; } // Check in left subarray else { // Update the value of // right right = mid - 1; } } return 1; } // Function to count the number of // distinct elements over the range // [L, R] in the sorted sequence static void countDistinct(int arr[], int L, int R) { // Stores the count of distinct // elements int count = 0; // Create the prefix sum array int pref[] = new int[arr.length + 1]; for (int i = 1; i <= arr.length; ++i) { // Update the value of count count += arr[i - 1]; // Update the value of pref[i] pref[i] = count; } // Calculating the first index // of L and R using binary search int left = binarysearch(pref, L); int right = binarysearch(pref, R); // Print the resultant count System.out.println( (right - left) + 1); } // Driver Code public static void main(String[] args) { int arr[] = { 3, 6, 7, 1, 8 }; int L = 3; int R = 7; countDistinct(arr, L, R); }} |
Python3
# Python3 program for the above approach# Function to find the first index# with value is at least elementdef binarysearch(array, right, element): # Update the value of left left = 1 # Update the value of right # Binary search for the element while (left <= right): # Find the middle element mid = (left + right // 2) if (array[mid] == element): return mid # Check if the value lies # between the elements at # index mid - 1 and mid if (mid - 1 > 0 and array[mid] > element and array[mid - 1] < element): return mid # Check in the right subarray elif (array[mid] < element): # Update the value # of left left = mid + 1 # Check in left subarray else: # Update the value of # right right = mid - 1 return 1# Function to count the number of# distinct elements over the range# [L, R] in the sorted sequencedef countDistinct(arr, L, R): # Stores the count of distinct # elements count = 0 # Create the prefix sum array pref = [0] * (len(arr) + 1) for i in range(1, len(arr) + 1): # Update the value of count count += arr[i - 1] # Update the value of pref[i] pref[i] = count # Calculating the first index # of L and R using binary search left = binarysearch(pref, len(arr) + 1, L) right = binarysearch(pref, len(arr) + 1, R) # Print the resultant count print(right - left + 1)# Driver Codeif __name__ == "__main__": arr = [ 3, 6, 7, 1, 8 ] L = 3 R = 7 countDistinct(arr, L, R)# This code is contributed by ukasp |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the first index// with value is at least elementstatic int binarysearch(int []array, int right, int element){ // Update the value of left int left = 1; // Update the value of right // Binary search for the element while (left <= right) { // Find the middle element int mid = (left + right / 2); if (array[mid] == element) { return mid; } // Check if the value lies // between the elements at // index mid - 1 and mid if (mid - 1 > 0 && array[mid] > element && array[mid - 1] < element) { return mid; } // Check in the right subarray else if (array[mid] < element) { // Update the value // of left left = mid + 1; } // Check in left subarray else { // Update the value of // right right = mid - 1; } } return 1;}// Function to count the number of// distinct elements over the range// [L, R] in the sorted sequencestatic void countDistinct(List<int> arr, int L, int R){ // Stores the count of distinct // elements int count = 0; // Create the prefix sum array int []pref = new int[arr.Count + 1]; for(int i = 1; i <= arr.Count; ++i) { // Update the value of count count += arr[i - 1]; // Update the value of pref[i] pref[i] = count; } // Calculating the first index // of L and R using binary search int left = binarysearch(pref, arr.Count + 1, L); int right = binarysearch(pref, arr.Count + 1, R); // Print the resultant count Console.Write(right - left + 1);}// Driver Codepublic static void Main(){ List<int> arr = new List<int>(){ 3, 6, 7, 1, 8 }; int L = 3; int R = 7; countDistinct(arr, L, R);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// Javascript program for the above approach// Function to find the first index// with value is at least elementfunction binarysearch(array, right, element){ // Update the value of left let left = 1; // Update the value of right // Binary search for the element while (left <= right) { // Find the middle element let mid = Math.floor((left + right / 2)); if (array[mid] == element) { return mid; } // Check if the value lies // between the elements at // index mid - 1 and mid if (mid - 1 > 0 && array[mid] > element && array[mid - 1] < element) { return mid; } // Check in the right subarray else if (array[mid] < element) { // Update the value // of left left = mid + 1; } // Check in left subarray else { // Update the value of // right right = mid - 1; } } return 1;} // Function to count the number of// distinct elements over the range// [L, R] in the sorted sequencefunction countDistinct(arr, L, R){ // Stores the count of distinct // elements let count = 0; // Create the prefix sum array let pref = Array.from( {length: arr.length + 1}, (_, i) => 0); for(let i = 1; i <= arr.length; ++i) { // Update the value of count count += arr[i - 1]; // Update the value of pref[i] pref[i] = count; } // Calculating the first index // of L and R using binary search let left = binarysearch(pref, arr.length + 1, L); let right = binarysearch(pref, arr.length + 1, R); // Print the resultant count document.write((right - left) + 1);}// Driver Codelet arr = [ 3, 6, 7, 1, 8 ];let L = 3;let R = 7;countDistinct(arr, L, R);// This code is contributed by susmitakundugoaldanga</script> |
Output
2
Time Complexity: O(log(N))
Auxiliary Space: O(N)
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!