দুটি আনসর্টেড অ্যারে arr1[] এবং arr2[] দেওয়া থাকলে, arr1[]-এর প্রতিটি এলিমেন্টের জন্য arr2[]-এ কতগুলো এলিমেন্ট সেটির চেয়ে কম বা সমান সেটা গণনা করতে হবে।
ইনপুট-১
N = 6, M = 9
arr1 = {1, 2, 5, 0, 6, 3}
arr2 = {0,0,1,2,1,3,4,6,8}
আউটপুট
4 5 7 2 8 6
সমাধানের পদ্ধতি
arr2[]-কে সর্ট করে বাইনারি সার্চ ব্যবহার করা হয়।
- arr1 এবং arr2-এর সাইজ m, n ইনপুট নিন।
- arr2[]-কে সর্ট করুন।
- arr1[]-এর প্রতিটি এলিমেন্টের জন্য বাইনারি সার্চ দিয়ে arr2[]-এ উপরের বাউন্ড (upper bound) বের করুন।
- ইন্ডেক্স + ১ হবে কাউন্ট।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void countInSecond(int *nums1, int *nums2, int m, int n) {
sort(nums2, nums2 + n);
for (int i = 0; i < m; i++) {
int s = 0, e = n - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (nums2[mid] <= nums1[i]) s = mid + 1;
else e = mid - 1;
}
cout << e + 1 << " ";
}
}
int main() {
int m = 6, n = 9;
int arr1[m] = {1,2,5,0,6,3};
int arr2[n] = {0,0,1,2,1,3,4,6,8};
countInSecond(arr1, arr2, m, n);
return 0;
}
আউটপুট
4 5 7 2 8 6
