समान अ‍ॅली एलिमेंट्स लीटकोड सोल्यूशनवर किमान मूव्ह्स


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद Coursera फॅक्टसेट खरंच जेपी मॉर्गन, गणिते मायक्रोसॉफ्ट स्विगी
ड्रॉब्रिज गणित

समस्या विधान

या समस्येमध्ये, आम्हाला एक दिले जाते अॅरे पूर्णांक तसेच, आम्हाला या अ‍ॅरेवर काही विशिष्ट ऑपरेशन्स करण्याची परवानगी आहे. एका ऑपरेशनमध्ये, आम्ही अ‍ॅरेमधील ”n - 1 ″ (कोणत्याही व्यतिरिक्त सर्व घटक) घटकांना 1 ने वाढवू शकतो.

आम्हाला सर्व अ‍ॅरे घटक समान करण्यासाठी आवश्यक किमान ऑपरेशन शोधण्याची आवश्यकता आहे.

उदाहरण

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

 

समान अ‍ॅली एलिमेंट्स लीटकोड सोल्यूशनवर किमान मूव्ह्सअ‍ॅप्रोच (मॅथ)

या समस्येमध्ये, आपल्याला अ‍ॅरेच्या सर्व अ‍ॅरे घटकांची संख्या वाढवून 1 ने वाढवू इच्छित असलेल्या संख्येचा संच निवडण्याची अडचण आहे. तथापि, अ‍ॅरे मधील 'एन - 1' घटक वाढविणे हे एक अ‍ॅरे घटक 1 ने कमी करण्यासारखेच आहे. हे असे आहे कारण सर्व घटकांचे समान झाल्यावर त्यांचे मूल्य काय आहे हे शोधण्याची आपली इच्छा नाही, त्याऐवजी आम्हाला हालचालींची संख्या शोधण्यात रस आहे. आता हे सहजपणे समजले आहे की आमचे ऑपरेशन अ‍ॅरे मधील एका घटकाचे 1 ने कमी होणार असल्याने आपल्याला अ‍ॅरे मधील सर्व घटक एरे मधील कमीतकमी घटकामध्ये रूपांतरित करणे आवश्यक आहे (कारण त्यामध्ये कोणतीही घट करण्याची आवश्यकता नाही. पुढील).

समान अ‍ॅरे इलिमेंटस लीटकोड सोल्यूशनच्या किमान मूव्ह्सची अंमलबजावणी

सी ++ प्रोग्राम

#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)जेव्हा आपण अ‍ॅरेमध्ये स्थिर मेमरी स्पेस वापरत आहोत.