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 integerint 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 Codeint 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 integerdef 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 Codeif __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 approachusing 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 integerfunction 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 arraylet arr = [ 1, 5, 4, 5, 6 ];// Number of querieslet Q = 3;// Array of querieslet query = [ 1, 4, 5 ];// Size of the arraylet N = arr.length;subarraysEndingWithX(arr, N, query, Q); |
Output
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 integerint 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 Codeint 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 approachimport java.util.*;class GFG{// Function to perform queries to count the// number of subarrays having given numbers// as the last integerstatic 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 Codepublic 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 integerdef 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 Codeif __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 approachusing 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 integerfunction 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> |
Output
1 3 6
Time Complexity: O(Q + 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!
