समान ऐरे एलीमेंट्स लेटकोड सॉल्यूशन के लिए न्यूनतम चाल


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब Coursera FactSet वास्तव में जेपी मॉर्गन मैथवर्क्स माइक्रोसॉफ्ट Swiggy
सीढ़ी मठ

समस्या का विवरण

इस समस्या में, हमें एक दिया जाता है सरणी पूर्णांकों का। साथ ही, हमें इस सरणी पर कुछ निश्चित कार्य करने की अनुमति है। एक ऑपरेशन में, हम 1 से सरणी में "n - 1 one (किसी एक को छोड़कर सभी तत्व) तत्वों को बढ़ा सकते हैं।

हमें सभी एरे तत्वों को समान बनाने के लिए आवश्यक न्यूनतम संचालनों को खोजने की आवश्यकता है।

उदाहरण

Array = {1 , 2 , 3}
3
Array = {1 , 1 , 1}
0

 

समान ऐरे एलीमेंट्स लेटकोड सॉल्यूशन के लिए न्यूनतम चालदृष्टिकोण (गणित)

इस समस्या में, संख्या के सेट को चुनना मुश्किल है जिसे आप सभी सरणी तत्वों के बराबर 1 से बढ़ाना चाहेंगे। हालाँकि, सरणी में 'N - 1' तत्वों को बढ़ाना एक सरणी तत्व को 1 से कम करने के समान है। ऐसा इसलिए है क्योंकि हम यह पता लगाने की इच्छा नहीं रखते हैं कि एक बार समान होने के बाद सभी तत्वों का मूल्य क्या होगा, बल्कि हम चाल की संख्या खोजने में रुचि रखते हैं। अब, यह सहज है कि चूंकि हमारा ऑपरेशन 1 से सरणी में ठीक एक तत्व को कम करना है, इसलिए हमें सरणी में मौजूद सभी तत्वों को सरणी में मौजूद न्यूनतम तत्व में बदलना होगा (क्योंकि इसमें किसी भी कमी की आवश्यकता नहीं है। आगे की)।

समान ऐरे एलीमेंट्स लेटकोड सॉल्यूशन के लिए न्यूनतम चाल के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

int minMoves(vector <int> nums) {
    int mn = *min_element(nums.begin() , nums.end()) , moves = 0;
    for(int &i : nums)
        moves += i - mn;
    return moves;
}

int main() {
    vector <int> nums = {1 , 2 , 3};
    cout << minMoves(nums) << endl;
    return 0;
}

जावा प्रोग्राम

import java.lang.*;
import java.util.*;

class min_moves {
    public static void main(String args[]) {
        int[] nums = {1 , 2 , 3};
        System.out.println(minMoves(nums));
    }

    public static int minMoves(int[] nums) {
        if(nums.length == 0)
            return 0;
        int mn = nums[0];
        for(int i = 0 ; i < nums.length ; i++) {
            mn = Math.min(mn , nums[i]);
        }

        int moves = 0;
        for(int i = 0 ; i < nums.length ; i++) {
            moves += nums[i] - mn;
        }

        return moves;
    }
}
3

समान ऐरे एलिमेंट्स लेटकोड सॉल्यूशन के लिए न्यूनतम चाल की जटिलता विश्लेषण

समय जटिलता

पर), एन = सरणी का आकार। हम पूरे सरणी को एक बार पार करते हैं।

अंतरिक्ष जटिलता 

ओ (1), क्योंकि हम सरणी में निरंतर मेमोरी स्पेस का उपयोग करते हैं।