صف میں برابر تمام عناصر کے ل make کم از کم آپریشن


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون BlackRock درگ ہدایت Flipkart بے شک Yandex
لڑی ہیکنگ

مسئلہ "صفوں میں تمام عناصر کو مساوی بنانے کے لئے کم سے کم آپریشن" یہ بتاتا ہے کہ آپ کو ایک درجہ دیا جاتا ہے صف کچھ کے ساتھ اشارے اس میں. آپ کو کم سے کم آپریشنز کا پتہ لگانا ہوگا جو سرنی کو برابر بنانے کے لئے کیا جاسکتا ہے۔

مثال کے طور پر

صف میں برابر تمام عناصر کے ل make کم از کم آپریشن

[ 1,3,2,4,1]
3

وضاحت

یا تو 3 گھٹاؤ کیے جاسکتے ہیں یا 3 مساوی صف برابر کرنے کے لئے بھی کیا جاسکتا ہے۔

[5,3,2,4,1]
4

وضاحت

یا تو 4 گھٹاؤ کیے جاسکتے ہیں یا 4 مساوی صف برابر کرنے کے لئے بھی کیا جاسکتا ہے۔

تمام عناصر کو مساوی بنانے کے لئے کم سے کم آپریشنز تلاش کرنے کے لئے الگورتھم

  1. اعلان a نقشہ.
  2. جبکہ میں << n ، لوپ جاری ہے
    1. نقشہ میں ہر عنصر کی سرنی عنصر اور تعدد کو اسٹور کریں۔
  3. سیٹ کریں "میکسکاؤنٹ" 0 پر.
  4. لوپ چیک کریں اگر جانچ پڑتال کریں "میکسکاؤنٹ" نقشہ میں کلید کی قدر سے کم ہے
    1. اگر حالت اطمینان بخش ہو تو پھر سیٹ کریں "میکسکاؤنٹ" کلید کی قدر میں
  5. واپسی (n - "میکساکونٹ")۔

وضاحت

ہمارے پاس ہے عددی صف ان پٹ کے طور پر ہمارا کام کم سے کم آپریشنز کا پتہ لگانا ہے جو کسی صف کو برابر بنانے کے لئے کیا جاسکتا ہے۔ ہم اس میں ایک نقشہ استعمال کرنے جارہے ہیں۔ نقشہ کا استعمال کرتے ہوئے ، ہم عناصر کو آسانی سے ان کی تعدد کے ساتھ اسٹور کرسکتے ہیں ، کیوں کہ تعیشات کارروائیوں کا پتہ لگانے میں کلیدی کردار ادا کرتے ہیں۔

ہم زیادہ سے زیادہ تعدد والے عنصر کو ڈھونڈنے جا رہے ہیں اور ہم صف کی لمبائی اور زیادہ سے زیادہ تعدد گنتی کے درمیان فرق واپس کردیں گے کیونکہ ہمارے پاس عنصر پہلے ہی موجود ہے جو ایک سرنی میں ہے جس کو دہرایا گیا ہے لہذا تمام عناصر کو یکساں بنانے میں کم کارروائیوں کی ضرورت ہے۔ کیونکہ یہ کسی خاص کو تبدیل کرنے کی بجائے ہے اور اسی وجہ سے (صف کی لمبائی- زیادہ سے زیادہ تعدد) یہ یہاں کام کرتا ہے۔

آئیے یہاں ایک مثال پر غور کریں:

مثال کے طور پر

ارر: {1، 5، 2، 1، 3، 2، 1}؛

سب سے پہلے عنصر سے شروع ہوکر ، ہم پوری صف کو عبور کرتے ہیں اور ہر عنصر کی تعدد گنتے ہیں اور اسے نقشے پر اسٹور کرتے ہیں۔

i = 0،

arr [i] = 1

countFreq = [1: 1]

میں = 1

arr [i] = 5

countFreq = [1: 1,5،1: XNUMX]

میں = 2

arr [i] = 2

countFreq = [1: 1,5،1,2: 1،XNUMX: XNUMX]

میں = 3

arr [i] = 1

countFreq = [1: 2,5،1,2: 1،1: 1] => یہاں ہمیں دو بار عنصر "XNUMX" مل جائے گا تاکہ XNUMX کی تعدد گنتی میں اضافہ ہوگا۔

میں = 4

arr [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

میں = 5

arr [i] = 2

countFreq = [1: 2,5،1,2: 2،3: 1: 2: 2] => یہاں ہمیں عنصر "XNUMX" دو بار مل جائے گا تاکہ تعدد کی گنتی XNUMX میں اضافہ ہوجائے گی۔

میں = 6

arr [i] = 1

countFreq = [1: 3,5،1,2: 2،3: 1: 1: 1] => یہاں ہمیں عنصر "XNUMX" تین بار مل جائے گا تاکہ تعدد کی گنتی میں XNUMX اضافہ ہوگا۔

اب شروع کریں "میکسکاؤنٹ" سے 0. اور ہر تعدد کی جانچ کریں اگر یہ اس سے زیادہ ہے "میکسکاؤنٹ"، اگر اس سے زیادہ تر معلوم ہوتا ہے تو پھر اس تعدد کی قیمت کو اس میں ذخیرہ کرلیں "میکسکاؤنٹ"

آخر کار ، ہمارے پاس سب سے بڑی تعدد ہوگی "میکسکاؤنٹ".

ہم واپس N- "میکسکاؤنٹ" => 7-3 = 4 ، یہ ہے کہ صف کو برابر بنانے کے ل we ہمیں کم سے کم 4 آپریشن کرنا چاہ.۔

ضابطے

C ++ تمام عناصر کو صف میں برابر بنانے کے لئے کم سے کم آپریشن ڈھونڈنا

#include <bits/stdc++.h>
using namespace std;

int getMinimumOperation (int arr[], int n)
{
  unordered_map<int, int> countFreq;
  for (int i=0; i<n; i++)
    countFreq[arr[i]]++;

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

صفوں میں تمام عناصر کو برابر کرنے کے لئے کم سے کم آپریشن معلوم کرنے کے لئے جاوا کوڈ

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


        return (n - maxCount);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.println(getMinimumOperations(arr, n));
    }
}
4

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔