തുല്യ അറേ ഘടകങ്ങളിലേക്ക് കുറഞ്ഞ നീക്കങ്ങൾ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ Coursera ഫാക്റ്റ്സെറ്റ് തീർച്ചയായും ചേസ് മാത്ത് വർക്ക്സ് മൈക്രോസോഫ്റ്റ് സ്വിഗ്ഗ്യ്
ഡ്രോബ്രിഡ്ജ് മഠം

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ. കൂടാതെ, ഈ ശ്രേണിയിൽ ഒരു നിശ്ചിത പ്രവർത്തനം നടത്താൻ ഞങ്ങളെ അനുവദിച്ചിരിക്കുന്നു. ഒരു പ്രവർത്തനത്തിൽ, നമുക്ക് അറേയിലെ ”n - 1 ″ (ഏതെങ്കിലും ഒരെണ്ണം ഒഴികെ എല്ലാ ഘടകങ്ങളും) 1 വർദ്ധിപ്പിക്കാൻ കഴിയും.

എല്ലാ അറേ ഘടകങ്ങളും തുല്യമാക്കുന്നതിന് ആവശ്യമായ ഏറ്റവും കുറഞ്ഞ പ്രവർത്തന എണ്ണം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

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

 

തുല്യ അറേ ഘടകങ്ങളിലേക്ക് കുറഞ്ഞ നീക്കങ്ങൾ ലീറ്റ്കോഡ് പരിഹാരംസമീപനം (കണക്ക്)

ഈ പ്രശ്‌നത്തിൽ‌, എല്ലാ അറേ ഘടകങ്ങൾക്കും തുല്യമായി നിങ്ങൾ‌ 1 വർദ്ധിപ്പിക്കാൻ‌ താൽ‌പ്പര്യപ്പെടുന്ന സംഖ്യകളുടെ സെറ്റ് തിരഞ്ഞെടുക്കുന്നതാണ് ബുദ്ധിമുട്ട്. എന്നിരുന്നാലും, അറേയിലെ 'N - 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

തുല്യ അറേ ഘടകങ്ങളിലേക്കുള്ള മിനിമം നീക്കങ്ങളുടെ സങ്കീർണ്ണത വിശകലനം ലീറ്റ്കോഡ് പരിഹാരം

സമയ സങ്കീർണ്ണത

O (N), അറേയുടെ N = വലുപ്പം. ഞങ്ങൾ മുഴുവൻ അറേയും ഒരു തവണ സഞ്ചരിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1), ഞങ്ങൾ നിരയിൽ സ്ഥിരമായ മെമ്മറി ഇടം ഉപയോഗിക്കുന്നതിനാൽ.