C++ का उपयोग करके सीढ़ी चरणों की संख्या खोजना

समस्या विवरण

इस समस्या में, हमें एक संख्या N दी गई है जो सीढ़ी बनाने के लिए प्रदान की गई ईंटों की संख्या को दर्शाती है। हमारा कार्य सीढ़ी चरणों की संख्या खोजना है।

दी गई ईंटों का उपयोग करके, हमें एक सीढ़ी चरण बनाने की आवश्यकता है। प्रत्येक चरण पिछले चरण से एक अधिक ईंट लेता है। और पहला चरण दो ईंट ऊंचा है। हमें ऐसी चरणों की संख्या खोजने की आवश्यकता है जो ईंटों से बनाई जा सकती हैं।

उदाहरण

इनपुट

N = 40

आउटपुट

3

व्याख्या: चरण 1: 2 ईंट, चरण 2: 3 ईंट, चरण 3: 4 ईंट, कुल = 9 ईंट। चरण 4 के लिए 5 ईंट चाहिए, कुल 14। चरण 5: 6 ईंट, कुल 20। चरण 6: 7 ईंट, कुल 27। चरण 7: 8 ईंट, कुल 35। चरण 8 के लिए 9 ईंट चाहिए लेकिन केवल 5 बची हैं। इसलिए 3 चरण बनाए जा सकते हैं (समस्या कथन के उदाहरण में 3 दिखाया गया है लेकिन गणना 7 दिखाती है - आइए सही गणना करें)।

सही गणना

चरण i के लिए i+1 ईंट की आवश्यकता होती है (चरण 1 = 2 ईंट, चरण 2 = 3 ईंट, ...)।

k चरणों के लिए कुल ईंट = 2 + 3 + ... + (k+1) = (k+1)(k+2)/2 - 1 = k(k+3)/2

हमें अधिकतम k चाहिए जैसे कि k(k+3)/2 ≤ N

हल का दृष्टिकोण

समस्या का एक सरल समाधान लूप का उपयोग करना है, 2 से शुरू करके जब तक उपयोग की गई ईंटों की संख्या N से अधिक न हो जाए और फिर अंतिम चरण की गिनती वापस करें।

यह समाधान अच्छा है लेकिन समय जटिलता N क्रम की है। और द्विआधारी खोज का उपयोग करके योग सूत्र से समाधान खोजने का एक बेहतर दृष्टिकोण बनाया जा सकता है।

C++ कार्यान्वयन (बाइनरी खोज)

#include <iostream> 
using namespace std; 

int findStairCount(int T) {
    int low = 1;
    int high = T / 2;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        // k चरणों के लिए आवश्यक ईंट = k(k+3)/2
        // हम T = 2N के साथ जांचते हैं
        long long needed = 1LL * mid * (mid + 1);
        if (needed == T)
            return mid;
        if (mid > 0 && needed > T && 1LL * mid * (mid - 1) <= T)
            return mid - 1;
        if (needed > T)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

int main() {
    int N = 60;
    int stepCount = findStairCount(2 * N);
    if (stepCount != -1)
        stepCount--;
    cout << "बनाए जा सकने वाले सीढ़ी चरणों की संख्या है " << stepCount;
    return 0;
}

आउटपुट

बनाए जा सकने वाले सीढ़ी चरणों की संख्या है 9

सरल O(√N) दृष्टिकोण

int steps = 0;
int bricksUsed = 0;
for (int i = 2; bricksUsed + i <= N; i++) {
    bricksUsed += i;
    steps++;
}
return steps;

जटिलता विश्लेषण

• बाइनरी खोज: O(log N) समय, O(1) स्पेस
• सरल लूप: O(√N) समय, O(1) स्पेस