మీరు లీట్‌కోడ్ పరిష్కారాన్ని పొందగల గరిష్ట నాణేల సంఖ్య


కఠినత స్థాయి మీడియం
సార్టింగ్

సమస్యల నివేదిక

“మీరు పొందగలిగే గరిష్ట నాణేల సంఖ్య” సమస్యలో మాకు 3 * n పైల్స్ నాణేలు ఇవ్వబడతాయి. నాణెం యొక్క ఈ పైల్స్ మీకు మరియు మీ ఇద్దరు స్నేహితులు ఆలిస్ మరియు బాబ్ లకు పంపిణీ చేయబడతాయి. నాణేల పైల్స్ పంపిణీకి నియమాలు క్రింది విధంగా ఉన్నాయి:

  1. మీరు ఏదైనా మూడు పైల్స్ ఎంచుకుంటారు.
  2. ఈ 3 పైల్స్ లో, ఆలిస్ గరిష్ట నాణేలను కలిగి ఉన్న పైల్ ను పొందుతాడు.
  3. రెండవ గరిష్ట నాణేలను కలిగి ఉన్న పైల్ మీకు లభిస్తుంది.
  4. బాబ్ తక్కువ సంఖ్యలో నాణేలతో పైల్ పొందుతారు.
  5. నాణేల పైల్స్ అన్ని పంపిణీ చేయబడని వరకు ఈ దశలను పునరావృతం చేయండి.

పై నియమాలను అనుసరించి, మీరు పొందగలిగే గరిష్ట నాణేలను మేము కనుగొనాలి.

ఉదాహరణ

piles = [9,8,7,6,5,1,2,3,4]
18

వివరణ:

మీరు ఈ క్రింది విధంగా పైల్స్ ఎంచుకుంటారు:

  • (9,8,1)
  • (7,6,2)
  • (5,4,3)

పైల్ ఎంపిక యొక్క ఈ మార్గం మీకు 18 నాణేలు ఉన్న గరిష్ట నాణేలను పొందటానికి దారి తీస్తుంది.

మీరు లీట్‌కోడ్ పరిష్కారాన్ని పొందగల గరిష్ట నాణేల కోసం విధానం

ఈ సమస్యను పరిష్కరించడానికి అన్ని ఉపాయాలు ప్రతిసారీ 3 పైల్స్ ఎంచుకునే మార్గం వెనుక ఉన్నాయి, అది మీకు గరిష్ట సంఖ్యలో నాణేలను పొందటానికి దారి తీస్తుంది.

  • బాబ్ తక్కువ సంఖ్యలో నాణేలతో పైల్ పొందుతాడు. కాబట్టి ప్రతిసారీ కనీస నాణేల సంఖ్యను కలిగి ఉన్న మిగిలిన పైల్స్ నుండి ఒక పైల్‌ని ఎంచుకుంటాము. 3 * n పైల్స్ నుండి తక్కువ సంఖ్యలో నాణేలతో బాబ్ అన్ని n పైల్స్ పొందుతారని ఇది నిర్ధారిస్తుంది.
  • ప్రతిసారీ గరిష్ట సంఖ్య నాణేలను కలిగి ఉన్న మిగిలిన పైల్స్ నుండి రెండు పైల్స్ ఎంచుకుంటాము. ఆలిస్ గరిష్ట నాణేలను కలిగి ఉన్న కుప్పను పొందుతాడు. మీరు రెండవ గరిష్ట సంఖ్య నాణేలతో పైల్ పొందుతారు.
  • గరిష్ట మరియు కనీస నాణేలతో పైల్స్ పొందడానికి, మేము చేస్తాము విధమైన శ్రేణి.
  • క్రింద చూపిన చిత్రం ఆలిస్, బాబ్ మరియు మీ మధ్య పైల్స్ పంపిణీని వివరిస్తుంది.

మీరు పొందగలిగే గరిష్ట నాణేలకు లీట్‌కోడ్ పరిష్కారం

అమలు

మీరు పొందగలిగే గరిష్ట నాణేల కోసం C ++ కోడ్

#include <bits/stdc++.h> 
using namespace std; 
    int maxCoins(vector<int>& piles) {
     sort(piles.begin(),piles.end());
        int n=piles.size();
        int ans=0;
        for(int i=n/3;i<n;i=i+2)
            ans+=piles[i];
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 9,8,7,6,5,1,2,3,4 }; 
 cout<<maxCoins(arr)<<endl; 
 return 0;
}
18

మీరు పొందగలిగే గరిష్ట నాణేల జావా కోడ్

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxCoins(int[] piles) {
          Arrays.sort(piles);
        int res = 0, n = piles.length;
        for (int i = n / 3; i < n; i += 2)
            res += piles[i];
        return res;
    }
  public static void main(String[] args) {
    int [] arr = {9,8,7,6,5,1,2,3,4}; 
    int ans=  maxCoins(arr);
    System.out.println(ans);
  }
}
18

మీరు లీట్‌కోడ్ పరిష్కారాన్ని పొందగల గరిష్ట నాణేల సంక్లిష్టత విశ్లేషణ

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

పై కోడ్ యొక్క సమయం సంక్లిష్టత O (nlogn) ఎందుకంటే మేము శ్రేణిని క్రమబద్ధీకరిస్తున్నాము. ఇక్కడ n అనేది శ్రేణి యొక్క పరిమాణం.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత O (1) ఎందుకంటే మేము జవాబును నిల్వ చేయడానికి వేరియబుల్ మాత్రమే ఉపయోగిస్తున్నాము.

ప్రస్తావనలు