मान लीजिए हमें n-वां अग्ली नंबर ढूंढने के लिए एक प्रोग्राम लिखना है। अग्ली नंबर वे पॉजिटिव इंटीजर्स हैं जो a या b या c से डिविजिबल होते हैं। उदाहरण के लिए, अगर n = 3 और a = 2, b = 3 और c = 5, तो आउटपुट 4 होगा, क्योंकि अग्ली नंबर्स हैं [2,3,4,5,6,8,9,10], तीसरा वाला 4 है।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
ok() नाम का एक मेथड बनाएं, जो x, a, b, c लेगा, यह निम्न की तरह काम करेगा:
return (x/a) + (x/b) + (x/c) - (x/lcm(a,b)) - (x/lcm(b,c)) - (x/lcm(a,c)) + (x/lcm(a, lcm(b,c)))
मेन मेथड से निम्न करें:
low := 1, high := 2 * (10^9)
जब तक low < high:
mid := low + (high - low) / 2
x := ok(mid, a, b, c)
अगर x >= n, तो high := mid, अन्यथा low := mid + 1
high लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli gcd(lli a, lli b){
return b == 0? a: gcd(b, a % b);
}
lli lcm(lli a, lli b){
return a * b / gcd(a, b);
}
lli ok(lli x, lli a, lli b, lli c){
return (x / a) + (x / b) + (x / c) - (x / lcm(a, b)) - (x / lcm(b, c)) - (x / lcm(a, c)) + (x / lcm(a, lcm(b, c)));
}
int nthUglyNumber(int n, int a, int b, int c) {
int low = 1;
int high = 2 * (int) 1e9;
while(low < high){
int mid = low + (high - low) / 2;
int x = ok(mid, a, b, c);
if(x >= n){
high = mid;
}
else low = mid + 1;
}
return high;
}
};
int main(){
Solution ob;
cout << (ob.nthUglyNumber(3,2,3,5));
}
इनपुट
3 2 3 5
आउटपुट
4