This is my solution to the following Coding Challenge – Find Num of Elements in a Range in O(1) with Preprocessing
given array and max element in array. Find no. of elements present between a given range in O(1). You can do one time processing of array. Solution
#include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std; class Solution { public: Solution(vector<int>& v) { sort(v.begin(), v.end()); for(unsigned int i=0; i<v.size(); ++i) m[v[i]] = i; } unsigned int count(const int a, const int b) { if(!(a < b)) throw runtime_error("Wrong Order"); if( (m.find(a) == m.end()) || (m.find(b) == m.end()) ) throw runtime_error("Not Found"); return m[b] - m[a] + 1; } private: unordered_map<int, unsigned int> m; }; int main() { // your code goes here int N; cin >> N; vector<int> data; for(int i=0; i<N; ++i) { int temp; cin >> temp; data.push_back(temp); } Solution sol(data); const auto left = 1; const auto right = 3; const auto res = sol.count(left, right); cout << "Left = " << left << ", Right = " << right << " --> Res = " << res << endl; return 0; } Notes – Even if typically for Algorithmic Coding Challenges a free function is good enough and using a class is over-engineering, in this specific I went for the class on purpose in order to possibly amortize the pre-processing cost by multiple calls to the count() method
