इस समस्या में, हमें एक संख्या N दी गई है जो सीढ़ी बनाने के लिए प्रदान की गई ईंटों की संख्या को दर्शाती है। हमारा काम f . करना है सीढ़ी के चरणों की संख्या बताएं ।
दी गई ईंटों का उपयोग करते हुए, हमें एक सीढ़ी बनाने की आवश्यकता है। प्रत्येक चरण एक और ईंट लेता है जो अंतिम चरण है। और पहला कदम दो ईंटों का है। हमें ऐसे कदमों की संख्या ज्ञात करनी होगी जो ईंटों से बनाए जा सकते हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
N = 40
आउटपुट
3
स्पष्टीकरण
चरण =1; आवश्यक ईंटें =2; उपयोग की गई कुल ईंटें =2; शेष ईंटें =38
चरण =2; आवश्यक ईंटें =3; उपयोग की गई कुल ईंटें =5; शेष ईंटें =35
चरण =3; आवश्यक ईंटें =4; उपयोग की गई कुल ईंटें =9; शेष ईंटें =31
चरण =4; आवश्यक ईंटें =5; उपयोग की गई कुल ईंटें =14; शेष ईंटें =26
चरण =5; आवश्यक ईंटें =6; उपयोग की गई कुल ईंटें =20; शेष ईंटें =20
चरण =6; आवश्यक ईंटें =7; उपयोग की गई कुल ईंटें =27; शेष ईंटें =13
चरण =7; आवश्यक ईंटें =8; उपयोग की गई कुल ईंटें =35; शेष ईंटें =5
आगे कोई कदम नहीं बनाया जा सकता क्योंकि 8वें चरण में 9 ईंटों की आवश्यकता होती है और केवल 5 ही मौजूद होते हैं।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान लूप का उपयोग करना है, 2 से शुरू होकर उपयोग की जाने वाली ईंटों की संख्या N से अधिक हो जाती है और फिर अंतिम चरण की गणना वापस कर दी जाती है।
यह समाधान अच्छा है लेकिन समय जटिलता क्रम N की है। और योग सूत्र और बाइनरी खोज का उपयोग करके समाधान खोजने के लिए एक बेहतर तरीका बनाया जा सकता है।
हमारे पास X है जो उपयोग की जाने वाली ईंटों की कुल संख्या है जो हमेशा (n*(n+1)) /2 से बनाई जाती है क्योंकि हमारे पास सभी आवश्यक ईंटों का योग है। इस मामले में, हमारे पास दो मानों में से किसी एक का समाधान है जो मध्य और मध्य से पाया जाता है - 1.
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <iostream>
using namespace std;
int findStairCount(int T){
int low = 1;
int high = T/2;
while (low <= high) {
int mid = (low + high) / 2;
if ((mid * (mid + 1)) == T)
return mid;
if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T)
return mid - 1;
if ((mid * (mid + 1)) > 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<<"The number of stair steps that can be made is "<<stepCount;
return 0;
} आउटपुट
The number of stair steps that can be made is 9