Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Hussam_Jdid's blog

Need some Help.
By Hussam_Jdid, history, 2 years ago, In English

If i have a sorted vector like this v={ 5,6,7,8,9,10,11 } how can i get the number of elements that are bigger than x? lets say x is 9 so the number of elements bigger than 9 equals 2 how can i code that?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +13 Vote: I do not like it

Upper bound

code
→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    lol , i did the exact same but when i compile it , it didn't give me any output and the program ended so i submitted the code anyway to ask what's wrong with it , and it got AC!! any idea why did that happen with my compiler? thanks.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      The below code requires knowledge of binary search.

      #include<bits/stdc++.h>
using namespace std;

// Upper bound: The smallest index such that arr[ind]>N(Strictly greater than).
int upperBound(vector<int> arr, int key){  // Here key is the element we want to find upperbound for.
    int low=0,high=arr.size()-1,ans=arr.size();  
    while(low<high){
        int mid=(low+high)/2;
        if(arr[mid]>key) {
            ans=mid;
            high=mid-1;
        }
        else low=mid+1;
    }
    return ans;
}

int main(){
    vector<int> v = {5, 6, 7, 8, 9, 15, 17};
    int num=9;
    int s= upperBound(v,num);
    cout << "Number of elements greater than " << num << " is " << v.size()-s <<endl;
    return 0;
}

      Hope this helps.

      → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      where did you submit ? Can you share the group link so I check the problem?

      → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

if the array is sorted you can use binary search to get the result in $$$O(log n)$$$ time, also C++ has a prebuilt function named upper_bound which does the same thing, if the array isn't sorted you can sort it first in $$$O(n log n)$$$ time and then use binary search or, iterate over the array and calculate it with a for/while loop in $$$O(n)$$$

→ Reply