मान लीजिए हमारे पास एक सरणी है, जो रोटेटेड सॉर्टेड सरणी है। हमें उन रोटेशन की संख्या ढूंढनी है जो सरणी को सॉर्ट करने के लिए आवश्यक हैं। (हम रोटेशन दाएं से बाएं मानेंगे।)
मान लीजिए सरणी ऐसी है: {15, 17, 1, 2, 6, 11}, तो हमें सरणी को दो बार रोटेट करना होगा ताकि यह सॉर्ट हो जाए। अंतिम क्रम {1, 2, 6, 11, 15, 17} होगा। यहां आउटपुट 2 है।
तर्क सरल है। यदि हम ध्यान दें, तो हम देख सकते हैं कि रोटेशन की संख्या न्यूनतम तत्व के इंडेक्स के मान के समान है। तो यदि हमें न्यूनतम तत्व मिल जाता है, तो उसका इंडेक्स परिणाम होगा।
उदाहरण
#include <iostream> using namespace std; int getMinIndex(int arr[], int n){ int index = 0; for(int i = 1; i<n; i++){ if(arr[i] < arr[index]){ index = i; } } return index; } int countNumberOfRotations(int arr[], int n){ return getMinIndex(arr, n); } int main() { int arr[] = {15, 17, 1, 2, 6, 11}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Number of required rotations: " << countNumberOfRotations(arr, n); }आउटपुट
Number of required rotations: 2
