समस्या कथन
N तत्वों की एक सरणी और एक पूर्णांक K दिया गया है। दी गई सरणी पर निम्न ऑपरेशन किसी भी संख्या में बार करना अनुमत है:
- K-वें तत्व को सरणी के अंत में डालें और सरणी के पहले तत्व को हटाएं।
कार्य सरणी के सभी तत्वों को समान बनाने के लिए आवश्यक न्यूनतम मूव्स की संख्या ढूंढना है। यदि संभव नहीं है तो -1 प्रिंट करें।
यदि arr[] = {1, 2, 3, 4, 5, 6} और k = 6, तो न्यूनतम 5 मूव्स आवश्यक हैं:
Move-1: {2, 3, 4, 5, 6, 6}
Move-2: {3, 4, 5, 6, 6, 6}
Move-3: {4, 5, 6, 6, 6, 6}
Move-4: {5, 6, 6, 6, 6, 6}
Move-5: {6, 6, 6, 6, 6, 6}
एल्गोरिदम
1. पहले हम a[k] को अंत में कॉपी करते हैं, फिर a[k+1] और इसी तरह 2. यह सुनिश्चित करने के लिए कि हम केवल समान तत्वों को कॉपी करते हैं, रेंज K से N तक के सभी तत्व समान होने चाहिए। हमें रेंज 1 से K में उन तत्वों को हटाना होगा जो a[k] के बराबर नहीं हैं 3. रेंज 1 से K में दाएं सबसे दूर के पद तक ऑपरेशन लागू करते रहें जो a[k] के बराबर नहीं है
C++ उदाहरण
#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinMoves(int *arr, int n, int k) {
int i;
for (i = k - 1; i < n; ++i) {
if (arr[i] != arr[k - 1]) return -1;
}
for (i = k - 1; i >= 0; --i) {
if (arr[i] != arr[k - 1]) return i + 1;
}
return 0;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6};
int k = 6;
cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl;
return 0;
}
आउटपुट
Minimum moves required = 5