Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में अग्ली नंबर III


मान लीजिए हमें 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

  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस

  1. - C++ में एडम नंबर जांचना

    इस खंड में हम देखेंगे कि दी गई संख्या एडम नंबर है या नहीं, इसकी जांच करने वाला प्रोग्राम कैसे लिखें। कोड में जाने से पहले देखते हैं कि एडम नंबर क्या है? एडम नंबर वह संख्या है, मान लीजिए n, यदि n का वर्ग और n के रिवर्स का वर्ग एक-दूसरे के रिवर्स हैं, तो वह संख्या एडम नंबर है। उदाहरण के लिए संख्या 13