लगातार लेटेकोड समाधान तक पत्थर हिल रहा है


कठिनाई स्तर आसान
में अक्सर पूछा Facebook
दिमागी कसरत

समस्या का विवरण

इस समस्या में, हमें ए, बी और सी के पदों पर तीन पत्थर दिए गए हैं। हमें निम्न चरण एक या एक से अधिक बार करके उन्हें लगातार बनाना है।
प्रत्येक चरण में, हम बाएं पत्थर या दाएं पत्थर को चुनेंगे और बाएं से दाएं पत्थर की सीमा के बीच में कहीं रख देंगे।
आइए चित्र के बाद इसे बेहतर तरीके से खड़ा करें:
लगातार लेटेकोड समाधान तक पत्थर हिल रहा है
हमें इन पत्थरों को लगातार बनाने के लिए ऐसे कदमों की न्यूनतम और अधिकतम संख्या का उत्तर देना होगा।

उदाहरण

a = 1, b = 2, c = 5
[1,2]

व्याख्या: पत्थर को ५ से ३ की ओर खिसकाएँ, या पत्थर को ५ से ४ से ३ की ओर ले जाएँ।

a = 4, b = 3, c = 2
[0,0]

हम कोई कदम नहीं उठा सकते।

a = 3, b = 5, c = 1
[1,2]

पत्थर को 1 से 4 तक स्थानांतरित करें; या पत्थर को 1 से 2 से 4 तक ले जाएं।

दृष्टिकोण

पहले बात करते हैं कि अधिकतम चरणों की गणना कैसे करें। क्या हम केवल यह नहीं कह सकते हैं कि चालों की संख्या अधिकतम तभी होगी जब चरम सीमा पर दोनों पत्थरों को 1 इकाई द्वारा मध्य पत्थर के करीब लाया जाए।
इस प्रकार बाएं पत्थर और मध्य पत्थर के बीच की स्थिति की संख्या + मध्य पत्थर और दाहिने पत्थर के बीच स्थिति की संख्या उन्हें लगातार बनाने के लिए हमारी अधिकतम संख्या होगी।
लगातार लेटेकोड समाधान तक पत्थर हिल रहा है
अब मुख्य समस्या यह है कि न्यूनतम चरणों की गणना कैसे की जाए। हम निम्नलिखित को समझकर न्यूनतम पता लगा सकते हैं स्थितियां.
चलो बाएं पत्थर और मध्य पत्थर के बीच के पदों की संख्या को स्थान कहते हैं और मध्य पत्थर और दाहिने पत्थर के बीच के पदों की संख्या है।
इन पत्थरों की प्रारंभिक स्थिति के बारे में निम्नलिखित 4 स्थितियों में से केवल एक ही कहा जा सकता है।

1. यदि पत्थरों में पहले से ही लगातार यानी lspace = 0 और rspace = 0 है तो min_steps = 0।

लगातार लेटेकोड समाधान तक पत्थर हिल रहा है2. यदि तीन पत्थरों में से दो लगातार हैं, यदि lspace = 0 या rspace = 0 है, तो हम केवल 1 कदम में मध्य पत्थर के पास सबसे दूर पत्थर रख सकते हैं, इस प्रकार min_steps = 1।

दिमागी कसरत3. यदि तीन पत्थरों में से किसी एक के बीच का स्थान 1 है, तो यदि lspace = 1 या rspace = 1 है। फिर, सबसे दूर के पत्थर को दो एकल पत्थरों के बीच रखा जा सकता है (ध्यान दें कि पत्थरों के पास सिर्फ एक ही चरण में एक ही स्थिति है)।
इसलिए, उन्हें लगातार बनाना केवल 1 चरण में हो सकता है। इस प्रकार, min_steps = 1।

दिमागी कसरत4. दोनों चरम पर पत्थरों को प्रत्येक चरण 1 के द्वारा मध्य पत्थरों के पड़ोसी में रखा जा सकता है। इस प्रकार, min_steps = 1 + 1 = 2।
लगातार लेटेकोड समाधान तक पत्थर हिल रहा है

कार्यान्वयन

लगातार लेटोकोड समाधान तक मूविंग स्टोन्स के लिए C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

लगातार लेटेकोड सॉल्यूशन तक स्टोन्स मूविंग के लिए जावा प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
vector<int> numMovesStones(int a, int b, int c) 
{
    int left=min(a,min(b,c));
    int right=max(a,max(b,c));
    int mid=(a!=left && a!=right )?a:(b!=left && b!=right)?b:c;
    int lspace=mid-left-1;
    int rspace=right-mid-1;
    int max=lspace+rspace,min=0;
    if(lspace==0 && rspace==0)min=0;
    else if(lspace==0 || rspace==0)min=1;
    else if(lspace==1 || rspace==1)min=1;
    else min=2;
    vector<int> ans{min,max};
    return ans;
}
int main()
{
   vector<int>ans=numMovesStones(1,2,5);
   cout<<ans[0]<<" "<<ans[1]<<endl;
}
1 2

लगातार लेटेकोड समाधान तक स्टोन्स को स्थानांतरित करने के लिए जटिलता विश्लेषण

समय जटिलता

ओ (1): हमने अपने एल्गोरिथ्म में सिर्फ साधारण सशर्त बयानों का उपयोग किया है। इस प्रकार, समय जटिलता हे (1) है।

अंतरिक्ष जटिलता 

ओ (1): बाएँ, दाएँ, क्षेत्र, 2 आकार के एन्स सरणी जैसे चरों के अलावा, हमने कोई अतिरिक्त स्थान नहीं बनाया है, इसलिए अंतरिक्ष जटिलता भी O (1) है।