मान लीजिए कि हमारे पास सकारात्मक पूर्णांकों की एक सरणी A है, तो हम कह सकते हैं कि सरणी वर्गाकार है यदि आसन्न तत्वों के प्रत्येक जोड़े के लिए, उनका योग एक पूर्ण वर्ग है। हमें वर्गाकार A के क्रमपरिवर्तनों की संख्या ज्ञात करनी है। दो क्रमपरिवर्तन A1 और A2 समान नहीं होंगे यदि और केवल यदि कुछ अनुक्रमणिका i ऐसा है कि A1[i] A2[i] के समान नहीं है।
इसलिए, यदि इनपुट [3,30,6] जैसा है, तो आउटपुट 2 होगा, क्योंकि हमारे पास [3,6,30], [30,6,3] जैसे दो क्रमपरिवर्तन हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें isSqr(), इसमें n लगेगा,
-
x :=n का वर्गमूल
-
सही लौटें जब (x * x) n के समान हो
-
-
एक फ़ंक्शन हल करें () को परिभाषित करें, यह एक सरणी लेगा a, idx,
-
यदि idx, a के आकार के समान है, तो -
-
(1 से गिनती बढ़ाएं)
-
वापसी
-
-
देखे गए एक सेट को परिभाषित करें
-
इनिशियलाइज़ i :=idx के लिए, जब i <का आकार, अपडेट (i से 1 तक बढ़ाएँ), करें -
-
अगर (idx 0 या isSqr(a[idx - 1] + a[i]) के समान है और a[i] विज़िट नहीं किया गया है तो -
-
स्वैप (ए [आईडीएक्स], ए [i])
-
हल करें (ए, आईडीएक्स + 1)
-
स्वैप (ए [आईडीएक्स], ए [i])
-
विज़िट किए गए में [i] डालें
-
-
-
-
मुख्य विधि से, निम्न कार्य करें -
-
गिनती :=0
-
हल करें (ए, 0)
-
वापसी की संख्या
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int count;
bool isSqr(lli n){
lli x = sqrt(n);
return x * x == n;
}
void solve(vector<int>& a, int idx){
if (idx == a.size()) {
count++;
return;
}
set<int> visited;
for (int i = idx; i < a.size(); i++) {
if ((idx == 0 || isSqr(a[idx - 1] + a[i])) &&
!visited.count(a[i])) {
swap(a[idx], a[i]);
solve(a, idx + 1);
swap(a[idx], a[i]);
visited.insert(a[i]);
}
}
}
int numSquarefulPerms(vector<int>& a){
count = 0;
solve(a, 0);
return count;
}
};
main(){
Solution ob;
vector<int> v = {3,30,6};
cout << (ob.numSquarefulPerms(v));
} इनपुट
{3,30,6} आउटपुट
2