Given an array arr[] and an array query[] consisting of Q queries, the task for every ith query is to count the number of subarrays having query[i] as the last element.
Note: Subarrays will be considered to be different for different occurrences of X.
Examples:
Input: arr[] = {1, 5, 4, 5, 6}, Q=3, query[]={1, 4, 5}
Output: 1 3 6
Explanation:
Query 1: Subarrays having 1 as the last element is {1}
Query 2: Subarrays having 4 as the last element are {4}, {5, 4}, {1, 5, 4}. Therefore, the count is 3.
Query 3: Subarrays having 5 as the last element are {1, 5}, {5}, {1, 5, 4, 5}, {5}, {4, 5}, {5, 4, 5}. Therefore, the count is 6.
.
Input: arr[] = {1, 2, 3, 3}, Q = 3, query[]={3, 1, 2}
Output: 7 1 2
Naive Approach: The simplest approach to solve the problem is to generate all the subarrays for each query and for each subarray, check if it consists of X as the last element.
Steps to implement-
- Run a loop on the query array
- For every query find all subarrays of array arr
- Then find the count of those subarrays whose last element is that query
- After finding the count simply print that
Code-
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to perform queries to count the // number of subarrays having given numbers // as the last integer int subarraysEndingWithX( int arr[], int N, int query[], int Q) { //Traverse the query for ( int m=0;m<Q;m++){ //Element that should be in the last of subarray int last=query[m]; //To store count of such subarray int count=0; //Find all subarray for ( int i=0;i<N;i++){ for ( int j=i;j<N;j++){ //When last element of subarray is //equal to query if (arr[j]==last){count++;} } } //Print the count of subarrays cout<<count<< " " ; } } // Driver Code int main() { // Given array int arr[] = { 1, 5, 4, 5, 6 }; // Number of queries int Q = 3; // Array of queries int query[] = { 1, 4, 5 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); subarraysEndingWithX(arr, N, query, Q); return 0; } |
Java
public class SubarraysEndingWithX { // Function to perform queries to count the number of subarrays // having given numbers as the last integer static void subarraysEndingWithX( int [] arr, int N, int [] query, int Q) { // Traverse the query for ( int m = 0 ; m < Q; m++) { // Element that should be in the last of subarray int last = query[m]; // To store count of such subarrays int count = 0 ; // Find all subarrays for ( int i = 0 ; i < N; i++) { for ( int j = i; j < N; j++) { // When last element of subarray is equal to query if (arr[j] == last) { count++; } } } // Print the count of subarrays System.out.print(count + " " ); } } public static void main(String[] args) { // Given array int [] arr = { 1 , 5 , 4 , 5 , 6 }; // Number of queries int Q = 3 ; // Array of queries int [] query = { 1 , 4 , 5 }; // Size of the array int N = arr.length; subarraysEndingWithX(arr, N, query, Q); } } |
Python3
# Function to perform queries to count the number of subarrays having given numbers as the last integer def subarrays_ending_with_x(arr, query): # Initialize a list to store the counts for each query result = [] # Traverse each query for last in query: # Initialize a count variable to store the number of subarrays count = 0 # Find all subarrays for i in range ( len (arr)): for j in range (i, len (arr)): # When the last element of the subarray is equal to the query if arr[j] = = last: count + = 1 # Append the count to the result list result.append(count) return result # Driver Code if __name__ = = "__main__" : # Given array arr = [ 1 , 5 , 4 , 5 , 6 ] # Number of queries Q = 3 # Array of queries query = [ 1 , 4 , 5 ] # Calculate the counts of subarrays for each query counts = subarrays_ending_with_x(arr, query) # Print the counts for each query for count in counts: print (count, end = " " ) |
C#
// C# program for the above approach using System; public class GFG { // Function to perform queries to count the // number of subarrays having given numbers // as the last integer public static void SubarraysEndingWithX( int [] arr, int N, int [] query, int Q) { // Traverse the queries for ( int m = 0; m < Q; m++) { // Element that should be at the // end of subarray int last = query[m]; // To store the count of such subarrays int count = 0; // Find all subarrays for ( int i = 0; i < N; i++) { for ( int j = i; j < N; j++) { // When the last element of subarray is // equal to the query if (arr[j] == last) { count++; } } } // Print the count of subarrays Console.Write(count + " " ); } } // Driver Code public static void Main() { // Given array int [] arr = { 1, 5, 4, 5, 6 }; // Number of queries int Q = 3; // Array of queries int [] query = { 1, 4, 5 }; // Size of the array int N = arr.Length; SubarraysEndingWithX(arr, N, query, Q); } } |
Javascript
// JavaScript program for the above approach // Function to perform queries to count the // number of subarrays having given numbers // as the last integer function subarraysEndingWithX( arr, N, query, Q) { //Traverse the query for (let m=0;m<Q;m++){ //Element that should be in the last of subarray let last=query[m]; //To store count of such subarray let count=0; //Find all subarray for (let i=0;i<N;i++){ for (let j=i;j<N;j++){ //When last element of subarray is //equal to query if (arr[j]==last) count++; } } //Print the count of subarrays console.log(count); } } // Driver Code // Given array let arr = [ 1, 5, 4, 5, 6 ]; // Number of queries let Q = 3; // Array of queries let query = [ 1, 4, 5 ]; // Size of the array let N = arr.length; subarraysEndingWithX(arr, N, query, Q); |
1 3 6
Time Complexity: O(Q×N2), because there were Q queries and we have to find all subarray for every query
Auxiliary Space: O(1), because no extra space has been used
Efficient Approach: To optimize the above approach, the idea is to use Hashing. Traverse the array and for every array element arr[i], search for its occurrence in the array. For every index, say idx, in which arr[i] is found, add (idx+1) to the count of subarrays having arr[i] as the last element.
Follow the steps below to solve the problem:
- Initialize an unordered map, say mp, to store the number of subarrays having X as the last element.
- Traverse the array and for every integer arr[i], increase mp[arr[i]] by (i+1).
- Traverse the array query[] and for each query query[i], print mp[query[i]].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to perform queries to count the // number of subarrays having given numbers // as the last integer int subarraysEndingWithX( int arr[], int N, int query[], int Q) { // Stores the number of subarrays having // x as the last element unordered_map< int , int > mp; // Traverse the array for ( int i = 0; i < N; i++) { // Stores current array element int val = arr[i]; // Add contribution of subarrays // having arr[i] as last element mp[val] += (i + 1); } // Traverse the array of queries for ( int i = 0; i < Q; i++) { int q = query[i]; // Print the count of subarrays cout << mp[q] << " " ; } } // Driver Code int main() { // Given array int arr[] = { 1, 5, 4, 5, 6 }; // Number of queries int Q = 3; // Array of queries int query[] = { 1, 4, 5 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); subarraysEndingWithX(arr, N, query, Q); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to perform queries to count the // number of subarrays having given numbers // as the last integer static void subarraysEndingWithX( int arr[], int N, int query[], int Q) { // Stores the number of subarrays having // x as the last element HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse the array for ( int i = 0 ; i < N; i++) { // Stores current array element int val = arr[i]; // Add contribution of subarrays // having arr[i] as last element if (mp.containsKey(val)) mp.put(val, mp.get(val)+(i+ 1 )); else mp.put(val, i+ 1 ); } // Traverse the array of queries for ( int i = 0 ; i < Q; i++) { int q = query[i]; // Print the count of subarrays System.out.print(mp.get(q)+ " " ); } } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1 , 5 , 4 , 5 , 6 }; // Number of queries int Q = 3 ; // Array of queries int query[] = { 1 , 4 , 5 }; // Size of the array int N = arr.length; subarraysEndingWithX(arr, N, query, Q); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approach # Function to perform queries to count the # number of subarrays having given numbers # as the last integer def subarraysEndingWithX(arr, N, query, Q): # Stores the number of subarrays having # x as the last element mp = {} # Traverse the array for i in range (N): # Stores current array element val = arr[i] # Add contribution of subarrays # having arr[i] as last element if val in mp: mp[val] + = (i + 1 ) else : mp[val] = mp.get(val, 0 ) + (i + 1 ); # Traverse the array of queries for i in range (Q): q = query[i] # Print the count of subarrays print (mp[q],end = " " ) # Driver Code if __name__ = = '__main__' : # Given array arr = [ 1 , 5 , 4 , 5 , 6 ] # Number of queries Q = 3 # Array of queries query = [ 1 , 4 , 5 ] # Size of the array N = len (arr) subarraysEndingWithX(arr, N, query, Q) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to perform queries to count the // number of subarrays having given numbers // as the last integer static void subarraysEndingWithX( int [] arr, int N, int [] query, int Q) { // Stores the number of subarrays having // x as the last element Dictionary< int , int > mp = new Dictionary< int , int >(); // Traverse the array for ( int i = 0; i < N; i++) { // Stores current array element int val = arr[i]; // Add contribution of subarrays // having arr[i] as last element if (mp.ContainsKey(val)) mp[val] = mp[val] + (i + 1); else mp[val] = i + 1; } // Traverse the array of queries for ( int i = 0; i < Q; i++) { int q = query[i]; // Print the count of subarrays Console.Write(mp[q] + " " ); } } // Driver Code public static void Main() { // Given array int [] arr = { 1, 5, 4, 5, 6 }; // Number of queries int Q = 3; // Array of queries int [] query = { 1, 4, 5 }; // Size of the array int N = arr.Length; subarraysEndingWithX(arr, N, query, Q); } } // This code is contributed by chitranayal. |
Javascript
<script> // JavaScript program for the above approach // Function to perform queries to count the // number of subarrays having given numbers // as the last integer function subarraysEndingWithX(arr, N, query, Q) { // Stores the number of subarrays having // x as the last element let mp = new Map(); // Traverse the array for (let i = 0; i < N; i++) { // Stores current array element let val = arr[i]; // Add contribution of subarrays // having arr[i] as last element if (mp.has(val)) mp.set(val, mp.get(val)+(i+1)); else mp.set(val, i+1); } // Traverse the array of queries for (let i = 0; i < Q; i++) { let q = query[i]; // Print the count of subarrays document.write(mp.get(q)+ " " ); } } // Driver Code // Given array let arr = [ 1, 5, 4, 5, 6 ]; // Number of queries let Q = 3; // Array of queries let query = [ 1, 4, 5 ]; // Size of the array let N = arr.length; subarraysEndingWithX(arr, N, query, Q); </script> |
1 3 6
Time Complexity: O(Q + N)
Auxiliary Space:O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!