Given an array containing N distinct elements. There are M queries, each containing an integer X and asking for the index of X in the array. For each query, the task is to perform linear search X from left to right and count the number of comparisons it took to find X and do the same thing right to left. In the end, print the total number of comparisons in both directions among all the queries.
Examples:
Input: arr[] = {1, 2}, q[] = {1, 2}
Output: 3, 3
For 1-based indexing
For 1st query : Number of comparisons from left to right is 1 and from right to left is 2
For 2nd query : Number of comparisons from left to right is 2 and from right to left is 1Input: arr[] = {-1, 2, 4, 5, 1}, q[] = {-1, 4, 2}
Output: 3, 7
Approach: Find the index at which X is present in the array say i (1-based indexing), the number of comparisons for left to right would be i and the number of comparisons for right to left would be (n – i + 1). All we need to do is to find the index quickly. It can be done by using a map in which key is the element’s value and value is the index.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of comparisons from left to right// and right to left in linear search among m queriespair<int, int> countCamparisions(int n, int arr[], int m, int qry[]){ int i; unordered_map<int, int> index; for (i = 1; i <= n; i++) { // arr[i] occurs at i index[arr[i]] = i; } // Count of comparisons for left to right and right to left int ltr = 0, rtl = 0; for (i = 1; i <= m; i++) { int x = qry[i]; ltr += index[x]; rtl += n - index[x] + 1; } return make_pair(ltr, rtl);}// Driver Codeint main(){ // -1 will be ignored as it is 1-based indexing int arr[] = { -1, 2, 4, 5, 1 }; int n = (sizeof(arr) / sizeof(arr[0])) - 1; int q[] = { -1, 4, 2 }; int m = (sizeof(q) / sizeof(q[0])) - 1; pair<int, int> res = countCamparisions(n, arr, m, q); cout << res.first << " " << res.second;} |
Java
// Java implementation of the approachimport java.util.HashMap;import java.util.Map;class GFG{// Function to return the count of // comparisons from left to right // and right to left in linear // search among m queries static Pair<Integer, Integer> countCamparisions(int n, int arr[], int m, int qry[]) { int i; HashMap<Integer,Integer> index = new HashMap<>(); for (i = 1; i <= n; i++) { // arr[i] occurs at i index.put(arr[i], i); } // Count of comparisons for left // to right and right to left int ltr = 0, rtl = 0; for (i = 1; i <= m; i++) { int x = qry[i]; ltr += index.get(x); rtl += n - index.get(x) + 1; } Pair<Integer, Integer> ans = new Pair<>(ltr, rtl); return ans; } // Driver Code public static void main(String []args) { // -1 will be ignored as it is 1-based indexing int arr[] = { -1, 2, 4, 5, 1 }; int n = arr.length - 1; int q[] = { -1, 4, 2 }; int m = q.length - 1; Pair<Integer, Integer> res = countCamparisions(n, arr, m, q); System.out.println(res.first + " " + res.second); }}class Pair<A, B> { A first; B second; public Pair(A first, B second) { this.first = first; this.second = second; }} // This code is contributed by Rituraj Jain |
Python3
# Python 3 implementation of the# above approach# Function to return the count of # comparisons from left to right # and right to left in linear search# among m queries def countCamparisions(n, arr, m, qry) : index = {} for i in range(1, n + 1) : # arr[i] occurs at i index[arr[i]] = i # Count of comparisons for left to # right and right to left ltr, rtl = 0, 0 for i in range(1, m + 1) : x = qry[i] ltr += index[x] rtl += n - index[x] + 1 return (ltr, rtl) # Driver Codeif __name__ == "__main__" : # -1 will be ignored as it # is 1-based indexing arr = [ -1, 2, 4, 5, 1 ] n = len(arr) - 1 q = [ -1, 4, 2 ] m = len(q) - 1 res = countCamparisions(n, arr, m, q) print(res[0], res[1]) # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{// Function to return the count of // comparisons from left to right // and right to left in linear // search among m queries static Pair<int, int> countCamparisions(int n, int []arr, int m, int []qry) { int i; Dictionary<int, int> index = new Dictionary<int, int>(); for (i = 1; i <= n; i++) { // arr[i] occurs at i index.Add(arr[i], i); } // Count of comparisons for left // to right and right to left int ltr = 0, rtl = 0; for (i = 1; i <= m; i++) { int x = qry[i]; ltr += index[x]; rtl += n - index[x] + 1; } Pair<int, int> ans = new Pair<int, int>(ltr, rtl); return ans; }// Driver Code public static void Main(String []args){ // -1 will be ignored as // it is 1-based indexing int []arr = { -1, 2, 4, 5, 1 }; int n = arr.Length - 1; int []q = { -1, 4, 2 }; int m = q.Length - 1; Pair<int, int> res = countCamparisions(n, arr, m, q); Console.WriteLine(res.first + " " + res.second);}}class Pair<A, B> { public A first; public B second; public Pair(A first, B second) { this.first = first; this.second = second; }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of comparisons from left to right// and right to left in linear search among m queriesfunction countCamparisions(n, arr, m, qry){ var i; var index = new Map(); for (i = 1; i <= n; i++) { // arr[i] occurs at i index.set(arr[i], i); } // Count of comparisons for left to right and right to left var ltr = 0, rtl = 0; for (i = 1; i <= m; i++) { var x = qry[i]; ltr += index.get(x); rtl += n - index.get(x) + 1; } return [ltr, rtl];}// Driver Code// -1 will be ignored as it is 1-based indexingvar arr = [-1, 2, 4, 5, 1];var n = arr.length - 1;var q = [-1, 4, 2];var m = q.length - 1;var res = countCamparisions(n, arr, m, q);document.write( res[0] + " " + res[1]);// This code is contributed by famously.</script> |
Output
3 7
Complexity Analysis:
- Time Complexity: O(N + M)
- 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!
