সমান অ্যারে এলিমেন্টস লেটকোড সমাধানে ন্যূনতম পদক্ষেপ


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল Coursera ফ্যাক্সেট প্রকৃতপক্ষে জে পি মরগ্যান গণিত মাইক্রোসফট Swiggy
ড্রব্রিজ ম্যাথ

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের একটি দেওয়া হয় বিন্যাস পূর্ণসংখ্যার এছাড়াও, আমাদের এই অ্যারেটিতে একটি নির্দিষ্ট সেট অপারেশন করার অনুমতি দেওয়া হয়। একটি ক্রিয়াকলাপে, আমরা অ্যারেতে "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

সমান অ্যারে উপাদানগুলি লেটকোড সমাধানে ন্যূনতম পদক্ষেপের জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), অ্যারের এন = আকার। আমরা একবারে পুরো অ্যারেটি অতিক্রম করি।

স্পেস জটিলতা ity 

ও (1), যেমন আমরা অ্যারেতে ধ্রুবক মেমরি স্পেস ব্যবহার করি।