मान लीजिए हमारे पास n तत्वों की एक सरणी A है (n विषम है)। A में पहले n प्राकृतिक संख्याओं का एक क्रमचय है। मान लीजिए एक फ़ंक्शन f(i) है जो 0 से n-2 की रेंज में एकल आर्गुमेंट i लेता है, और ऑपरेशन करता है: यदि A[i] > A[i+1], तो A[i] और A[i+1] के मानों को स्वैप करें। हमें सरणी A को पहली बार क्रमबद्ध करने के लिए पुनरावृत्तियों की संख्या गिननी है।
उदाहरण के लिए, यदि इनपुट A = [4, 5, 7, 1, 3, 2, 6] है, तो आउटपुट 5 होगा, क्योंकि प्रत्येक पुनरावृत्ति के बाद सरणी की स्थिति इस तरह है: [4, 5, 1, 7, 2, 3, 6], [4, 1, 5, 2, 7, 3, 6], [1, 4, 2, 5, 3, 7, 6], [1, 2, 4, 3, 5, 6, 7], [1, 2, 3, 4, 5, 6, 7]।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := size of A f := 0 Ans := 0 for initialize Ans := 0, do: f := 0 for initialize j := 0, when j < n - 1, update (increase j by 1), do: if A[j] > A[j + 1], then: f := 1 if not f is non-zero, then: Come out from the loop for initialize j := (Ans AND 1), when j < n - 1, update j := j + 2, do: if A[j] > A[j + 1], then: swap A[j] and A[j + 1] (increase Ans by 1) return Ans
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(vector A){ int n = A.size(); bool f = 0; int Ans = 0; for (Ans = 0;;){ f = 0; for (int j = 0; j < n - 1; j++) if (A[j] > A[j + 1]) f = 1; if (!f) break; for (int j = (Ans & 1); j < n - 1; j += 2) if (A[j] > A[j + 1]) swap(A[j], A[j + 1]); Ans++; } return Ans; } int main(){ vector A = { 4, 5, 7, 1, 3, 2, 6 }; cout << solve(A) << endl; }
इनपुट
{ 4, 5, 7, 1, 3, 2, 6 }आउटपुट
5