গেস গেম: প্লেয়ার ১ ১ থেকে n পর্যন্ত একটি নম্বর বেছে নেয়। প্লেয়ার ২ অনুমান করবে। প্রতিবার ভুল অনুমানে প্লেয়ার ১ বলে দেবে "উচ্চ" বা "নিম্ন"। guess(num) ফাংশন: -1 (নম্বর নিম্ন), 1 (নম্বর উচ্চ), 0 (মিল)। বাইনারি সার্চ দিয়ে নম্বরটি বের করুন।
উদাহরণ: n=10, pick=5 হলে আউটপুট ৫।
সমাধানের ধাপসমূহ
- l := 1, r := n।
- যখন l <= r:
- m := l + (r-l)/2।
- যদি guess(m) == 0, m রিটার্ন করুন।
- যদি guess(m) == -1, r = m-1।
- অন্যথায় l = m+1।
- 0 রিটার্ন করুন (যদি না পাওয়া যায়)।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int number;
int guess(int num) {
if (number > num) return 1;
if (number < num) return -1;
return 0;
}
public:
Solution(int n) { number = n; }
int guessNumber(int n) {
int l=1, r=n, m;
while (l <= r) {
m = l + (r-l)/2;
if (guess(m) == 0) return m;
if (guess(m) == -1) r = m-1;
else l = m+1;
}
return 0;
}
};
int main() {
Solution ob(5); // pick = 5
cout << ob.guessNumber(10);
return 0;
}
ইনপুট
5,10
আউটপুট
5
