समस्या कथन
N तत्वों की एक सरणी और एक पूर्णांक K को देखते हुए, इसे दिए गए सरणी पर किसी भी संख्या में निम्नलिखित ऑपरेशन करने की अनुमति है -
-
K वें . डालें सरणी के अंत में तत्व और सरणी के पहले तत्व को हटा दें।
कार्य सरणी के सभी तत्वों को समान बनाने के लिए आवश्यक न्यूनतम संख्या में चालों को खोजना है। प्रिंट -1 अगर संभव न हो तो
If arr[] = {1, 2, 3, 4, 5, 6} and k = 6 then minimum 5 moves are
required:
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. First we copy a[k] to the end, then a[k+1] and so on 2. To make sure that we only copy equal elements, all elements in the range K to N should be equal. We need to remove all elements in range 1 to K that are not equal to a[k] 3. Keep applying operations until we reach the rightmost term in range 1 to K that is not equal to a[k].
उदाहरण
#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