એરેમાં બધા તત્વો સમાન બનાવવા માટે ન્યૂનતમ કામગીરી


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન બ્લેકરોક સિટાડેલ ડાયરેક્ટિ ફ્લિપકાર્ટ ખરેખર યાન્ડેક્ષ
અરે હેશિંગ

સમસ્યા "એરેમાં બધા તત્વોને સમાન બનાવવા માટે ન્યૂનતમ કામગીરી" જણાવે છે કે તમને એ એરે કેટલાક સાથે પૂર્ણાંક તેમાં. તમારે ન્યૂનતમ કામગીરી શોધવા પડશે જે એરેને સમાન બનાવવા માટે કરી શકાય છે.

ઉદાહરણ

એરેમાં બધા તત્વો સમાન બનાવવા માટે ન્યૂનતમ કામગીરી

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

સમજૂતી

ક્યાં સરવાળો બનાવવા માટે 3 બાદબાકી કરી શકાય છે અથવા 3 ઉમેરાઓ કરી શકાય છે.

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

સમજૂતી

ક્યાં સરવાળો બનાવવા માટે 4 બાદબાકી કરી શકાય છે અથવા 4 ઉમેરાઓ કરી શકાય છે.

બધા તત્વોને સમાન બનાવવા માટે ન્યૂનતમ કામગીરી શોધવા માટે એલ્ગોરિધમ

  1. ઘોષણા કરો એ નકશો.
  2. જ્યારે હું <એન, લૂપ ચાલુ રહે છે
    1. નકશામાં દરેક તત્વની એરે તત્વ અને ફ્રીક્વન્સીઝ સ્ટોર કરો.
  3. સેટ "મેક્સકાઉન્ટ" 0 પર.
  4. લૂપ ઉપર તપાસ કરવી જો "મેક્સકાઉન્ટ" નકશામાં કીની કિંમત કરતા ઓછી છે
    1. જો સ્થિતિ સંતોષે, તો પછી સેટ કરો "મેક્સકાઉન્ટ" કી ની કિંમત.
  5. વળતર (n - "મહત્તમ રકમ").

સમજૂતી

અમારી પાસે છે પૂર્ણાંક એરે ઇનપુટ તરીકે. અમારું કાર્ય એ ન્યૂનતમ કામગીરી શોધવા માટે છે જે એરેને સમાન બનાવવા માટે કરી શકાય છે. અમે તેમાં નકશો વાપરવા જઈ રહ્યા છીએ. નકશાનો ઉપયોગ કરીને, અમે તત્વોને તેમની આવર્તન સાથે સરળતાથી સ્ટોર કરી શકીએ છીએ, કારણ કે કામગીરી શોધવા માટે ફ્રીક્વન્સીઝ મુખ્ય ભૂમિકા ભજવે છે.

આપણે મહત્તમ આવર્તન સાથે તત્વ શોધીશું અને અમે એરેની લંબાઈ અને મહત્તમ આવર્તન ગણતરી વચ્ચેનો તફાવત પાછો આપીશું કારણ કે આપણી પાસે એરેમાં પહેલાથી જ એલિમેન્ટ છે જે પુનરાવર્તિત થાય છે તેથી બધા ઘટકોને સમાન બનાવવા માટે ઓછા ઓપરેશન લે છે. કારણ કે તે કોઈ વિશિષ્ટને બદલવાને બદલે છે અને તેથી જ (એરેની લંબાઈ-મહત્તમ આવર્તન) તે અહીં કાર્ય કરે છે.

ચાલો અહીં એક ઉદાહરણ ધ્યાનમાં લઈએ:

ઉદાહરણ

અરર: {1, 5, 2, 1, 3, 2, 1};

પ્રથમ સૌથી તત્વથી શરૂ કરીને, અમે આખા એરેને વટાવીએ છીએ અને દરેક તત્વની આવર્તનની ગણતરી કરીએ છીએ અને તેને નકશા પર સંગ્રહિત કરીએ છીએ.

i = 0,

arr [i] = 1

ગણતરી ફ્રેક = [1: 1]

હું = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

હું = 2

arr [i] = 2

ગણતરીની ફ્રેક = [1: 1,5: 1,2: 1]

હું = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => અહીં આપણે બે વાર “1” તત્વ શોધીશું જેથી 1 ની આવર્તન સંખ્યા વધશે.

હું = 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 ની આવર્તન સંખ્યા વધશે.

હું = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => અહીં આપણે ત્રણ વખત "1" તત્વ શોધીશું જેથી 1 ની આવર્તન સંખ્યા વધશે.

હવે પ્રારંભ કરો "મેક્સકાઉન્ટ" થી 0. અને દરેક આવર્તન તપાસો જો તે વધારે છે "મેક્સકાઉન્ટ", જો વધારે હોવાનું જણાય, તો પછી તે આવર્તનનું મૂલ્ય આમાં સંગ્રહિત કરો "મેક્સકાઉન્ટ"

અંતે, અમારી પાસે સૌથી મોટી આવર્તન હશે "મેક્સકાઉન્ટ".

અમે એન પાછા ફરો "મેક્સકાઉન્ટ" => -7--3 =,, એરે સમાન બનાવવા માટે આપણે ઓછામાં ઓછું operations ઓપરેશન કરવું જોઈએ.

કોડ

એરેમાં બધા તત્વો સમાન બનાવવા માટે ન્યૂનતમ કામગીરી શોધવા માટે સી ++

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.