मान लीजिए हमारे पास दो पूर्णांक N और K हैं। हमें 1 से N तक के पूर्णांकों का एक क्रमचय ढूंढना है जैसे कि उन सूचकांकों (1-आधारित इंडेक्सिंग) की संख्या जहां gcd(P[i], i) > 1 है, ठीक K हो। इसलिए यदि N = 4 और K = 3, तो आउटपुट [1, 2, 3, 4] होगा, क्योंकि gcd(1, 1) = 1, gcd(2, 2) = 2, gcd(3, 3) = 3, gcd(4, 4) = 4
यदि हम ध्यान से देखें, तो हम पा सकते हैं कि gcd(i, i+1) = 1, gcd(1, i) = 1 और gcd(i, i) = i। चूंकि किसी भी संख्या और 1 का GCD हमेशा 1 होता है, K लगभग N - 1 हो सकता है। उस क्रमचय पर विचार करें जहां P[i] = i। उन सूचकांकों की संख्या जहां gcd(P[i], i) > 1, N - 1 होगी। यदि हम 1 को छोड़कर दो लगातार तत्वों को स्वैप करते हैं, तो ऐसे सूचकांकों की संख्या ठीक 2 से कम हो जाएगी, और 1 के साथ स्वैप करने पर ठीक 1 से कम हो जाएगी।
उदाहरण
#include<iostream> using namespace std; void findPermutation(int n, int k) { if (k >= n || (n % 2 == 0 && k == 0)) { cout << -1; return; } int P[n + 1]; for (int i = 1; i <= n; i++) P[i] = i; int count = n - 1; for (int i = 2; i < n; i+=2) { if (count - 1 > k) { swap(P[i], P[i + 1]); count -= 2; } else if (count - 1 == k) { swap(P[1], P[i]); count--; } else break; } for (int i = 1; i <= n; i++) cout << P[i] << " "; } int main() { int n = 5, k = 3; cout << "Permutation is: "; findPermutation(n, k); } आउटपुट
Permutation is: 2 1 3 4 5
