శ్రేణిలో అన్ని అంశాలను సమానంగా చేయడానికి కనీస ఆపరేషన్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ నలుపు రాయి సిటాడెల్ డైరెక్టి ఫ్లిప్కార్ట్ నిజానికి Yandex
అర్రే హ్యాషింగ్

“అన్ని అంశాలను శ్రేణిలో సమానంగా చేయడానికి కనీస ఆపరేషన్” అనే సమస్య మీకు ఇవ్వబడింది అమరిక కొన్ని తో పూర్ణాంకాల అందులో. శ్రేణిని సమానంగా చేయడానికి మీరు చేయగలిగే కనీస కార్యకలాపాలను మీరు కనుగొనాలి.

ఉదాహరణ

శ్రేణిలో అన్ని అంశాలను సమానంగా చేయడానికి కనీస ఆపరేషన్

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

వివరణ

3 వ్యవకలనాలు చేయవచ్చు లేదా సమాన శ్రేణిని చేయడానికి 3 చేర్పులు చేయవచ్చు.

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

వివరణ

4 వ్యవకలనాలు చేయవచ్చు లేదా సమాన శ్రేణిని చేయడానికి 4 చేర్పులు చేయవచ్చు.

అన్ని అంశాలను సమానంగా చేయడానికి కనీస కార్యకలాపాలను కనుగొనడానికి అల్గోరిథం

  1. ప్రకటించండి a చిహ్నం.
  2. నేను <n అయితే, లూప్ కొనసాగుతుంది
    1. ప్రతి మూలకం యొక్క శ్రేణి మూలకం మరియు పౌన encies పున్యాలను మ్యాప్‌లో నిల్వ చేయండి.
  3. సెట్ “మాక్స్కౌంట్” 0 కు.
  4. ఉంటే లూప్ చెక్ మీద మళ్ళించడం “మాక్స్కౌంట్” మ్యాప్‌లోని కీ విలువ కంటే తక్కువ
    1. పరిస్థితి సంతృప్తికరంగా ఉంటే, అప్పుడు సెట్ చేయండి “మాక్స్కౌంట్” కీ విలువకు.
  5. తిరిగి (n - “maxCount”).

వివరణ

మాకు ఒక ఉంది పూర్ణ సంఖ్య అమరిక ఇన్‌పుట్‌గా. శ్రేణిని సమానంగా చేయడానికి చేయగలిగే కనీస కార్యకలాపాలను కనుగొనడం మా పని. మేము దానిలో ఒక మ్యాప్‌ను ఉపయోగించబోతున్నాము. మ్యాప్‌ను ఉపయోగించి, మూలకాలను వాటి పౌన encies పున్యాలతో సులభంగా నిల్వ చేయవచ్చు, ఎందుకంటే కార్యకలాపాలను తెలుసుకోవడానికి పౌన encies పున్యాలు కీలక పాత్ర పోషిస్తాయి.

మేము గరిష్ట పౌన frequency పున్యంతో మూలకాన్ని కనుగొనబోతున్నాము మరియు శ్రేణి యొక్క పొడవు మరియు గరిష్ట పౌన frequency పున్య గణన మధ్య వ్యత్యాసాన్ని మేము తిరిగి ఇస్తాము ఎందుకంటే మనకు ఇప్పటికే ఒక శ్రేణిలో మూలకం ఉంది, ఇది పునరావృతమవుతుంది కాబట్టి అన్ని మూలకాలను ఒకేలా చేయడానికి తక్కువ ఆపరేషన్లు అవసరం ఇది ఒక ప్రత్యేకమైనదాన్ని మార్చడం కంటే మరియు అందువల్ల (శ్రేణి యొక్క పొడవు- గరిష్ట పౌన frequency పున్యం) ఇది ఇక్కడ పనిచేస్తుంది.

ఇక్కడ ఒక ఉదాహరణను పరిశీలిద్దాం:

ఉదాహరణ

arr: {1, 5, 2, 1, 3, 2, 1};

మొట్టమొదటి మూలకం నుండి ప్రారంభించి, మేము మొత్తం శ్రేణిని దాటి, ప్రతి మూలకం యొక్క ఫ్రీక్వెన్సీని లెక్కించి, దానిని మ్యాప్‌లో నిల్వ చేస్తాము.

i = 0,

arr [i] = 1

countFreq = [1: 1]

i = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

i = 2

arr [i] = 2

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

i = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => ఇక్కడ మనం “1” మూలకాన్ని రెండుసార్లు కనుగొంటాము కాబట్టి 1 యొక్క ఫ్రీక్వెన్సీ కౌంట్ పెరుగుతుంది.

i = 4

arr [i] = 3

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

i = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => ఇక్కడ మనం “2” మూలకాన్ని రెండుసార్లు కనుగొంటాము కాబట్టి ఫ్రీక్వెన్సీ కౌంట్ 2 పెరుగుతుంది.

i = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => ఇక్కడ మనం “1” మూలకాన్ని మూడుసార్లు కనుగొంటాము కాబట్టి 1 యొక్క ఫ్రీక్వెన్సీ కౌంట్ పెరుగుతుంది.

ఇప్పుడు ప్రారంభించండి “మాక్స్కౌంట్” నుండి 0. మరియు ప్రతి ఫ్రీక్వెన్సీ కంటే ఎక్కువ ఉంటే తనిఖీ చేయండి “మాక్స్కౌంట్”, ఎక్కువ అనిపిస్తే, ఆ ఫ్రీక్వెన్సీ విలువను నిల్వ చేయండి “మాక్స్కౌంట్”

చివరికి, మనకు గొప్ప పౌన frequency పున్యం ఉంటుంది “మాక్స్కౌంట్”.

మేము తిరిగి n- “మాక్స్కౌంట్” => 7-3 = 4, అంటే శ్రేణిని సమానంగా చేయడానికి మనం కనీసం 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.