BinarySearch/CountOccurance.cpp at main · AnuragJha003/BinarySearch · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//{ Driver Code Starts

#include<bits/stdc++.h>

using namespace std;


// } Driver Code Ends
//User function template for C++
class Solution{
public:
	/* if x is present in arr[] then returns the count
		of occurrences of x, otherwise returns 0. */
	int count(int arr[], int n, int x) {
	    // code here
	    /*unordered_map<int,int>mp;
	    for(int i=0;i<n;i++){
	        mp[arr[i]]++;
	    }
	    return mp[x];*/
	    int left=0,right=n-1,first=-1;

    while(left<=right){

        int mid= right+(left-right)/2;

        if(arr[mid]==x){

            first=mid;

            right=mid-1;

        }

        else if(arr[mid]<x) left=mid+1;

        else right=mid-1;

    }

    int last=-1;

    left=0;

    right=n-1;

    while(left<=right){

        int mid=right+(left-right)/2;

        if(arr[mid]==x){

            last=mid;

            left=mid+1;

        }

        else if(arr[mid]<x) left=mid+1;

        else right=mid-1;

    }

    if(first==-1 && last ==-1)return 0;

    else return {last-first+1};
	}
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        int arr[n];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        Solution ob;
        auto ans = ob.count(arr, n, x);
        cout << ans << "\n";
    }
    return 0;
}

// } Driver Code Ends

https://practice.geeksforgeeks.org/problems/number-of-occurrence2259/1?utm_source=youtube&utm_medium=collab_striver_ytdescription&utm_campaign=number-of-occurrence