C++ का उपयोग करके सरणी से हटाए गए अंतिम तत्व की स्थिति खोजना

समस्या विवरण

इस समस्या में, हमें आकार N की एक सरणी arr[] और एक पूर्णांक मान M दिया गया है। हमारा कार्य सरणी से हटाए गए अंतिम तत्व की स्थिति खोजना है।

सरणी से मानों को हटाना निम्नलिखित ऑपरेशनों पर आधारित है:

• सरणी में एक तत्व arr[i] के लिए। यदि arr[i] > M, तो मान को पॉप करें और arr[i] - M को सरणी के अंत में पुश करें। अन्यथा इसे सरणी से हटा दें।

ऑपरेशन तब तक करें जब तक सरणी में तत्व हैं।

उदाहरण

इनपुट

arr[] = {5, 4, 8}, M = 3

आउटपुट

3

व्याख्या

{5, 4, 8} → {4, 8, 2} → {8, 1, 2} → {1, 2, 5} → {2, 5} → {5} → {2} → खाली सरणी।
अंतिम हटाया गया मान 8 है, स्थिति 3 है।

हल का दृष्टिकोण

समस्या का एक सरल समाधान इस तथ्य का उपयोग करके हटाए जाने वाले अंतिम मान को खोजना है कि प्रत्येक मान जो अंत में हटाया जाता है उसका ceil(arr[i] / M) का सबसे बड़ा मान होता है।

उन तत्वों की स्थिति खोजने के लिए जो सरणी से अंत में बाहर निकलते हैं, हम सरणी को पार करेंगे और ceil(arr[i] / M) के अधिकतम मान वाली स्थिति को संग्रहीत करेंगे।

एल्गोरिदम

1. प्रत्येक तत्व के लिए, ceil(arr[i] / M) की गणना करें = (arr[i] + M - 1) / M
2. इस मान का अधिकतम मान खोजें
3. यदि एकाधिक तत्वों का समान अधिकतम मान है, तो अंतिम वाला (सबसे बड़ा इंडेक्स) उत्तर है
4. 1-आधारित इंडेक्स वापस करें

C++ कार्यान्वयन

#include <iostream> 
using namespace std; 

int findLastRemPos(int arr[], int n, int m) {
    // ceil(arr[i] / m) की गणना करें
    for (int i = 0; i < n; i++) {
        arr[i] = (arr[i] + m - 1) / m;  // सीलिंग विभाजन
    }
    
    int lastRemPos = -1, largestVal = -1;
    // अंत से पार करें ताकि अंतिम घटना मिले
    for (int i = n - 1; i >= 0; i--) {
        if (largestVal < arr[i]) {
            largestVal = arr[i];
            lastRemPos = i;
        }
    }
    
    return lastRemPos + 1; // 1-आधारित इंडेक्स
}

int main() {
    int arr[] = {5, 4, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << "सरणी में अंतिम हटाए गए तत्व की स्थिति है " << findLastRemPos(arr, n, m);
    return 0;
}

आउटपुट

सरणी में अंतिम हटाए गए तत्व की स्थिति है 3

जटिलता विश्लेषण

• समय जटिलता: O(N)
• स्पेस जटिलता: O(1)

मुख्य अंतर्दृष्टि

तत्व arr[i] को ठीक ceil(arr[i]/M) बार संसाधित किया जाएगा जब तक यह हटाया नहीं जाता। सबसे अधिक ऑपरेशन की आवश्यकता वाला तत्व अंत में हटाया जाएगा। टाई में, मूल सरणी में बाद में आने वाला तत्व बाद में हटाया जाता है।