అతిపెద్ద గ్రూప్ లీట్‌కోడ్ పరిష్కారాన్ని లెక్కించండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది మెర్కారి
అర్రే

కౌంట్ కంప్లీట్ గ్రూప్ లీట్‌కోడ్ సొల్యూషన్ సమస్య మాకు ఒక పూర్ణాంకాన్ని అందిస్తుంది. మేము 1 మరియు n (కలుపుకొని) మధ్య ప్రతి సంఖ్య యొక్క అంకెల మొత్తాన్ని కనుగొనవలసి ఉంది. అప్పుడు మేము సంఖ్యలను ఒకే అంకెలతో సమూహపరుస్తాము మరియు గణనను ఉంచుతాము. అప్పుడు మేము సమూహాల సంఖ్యను గరిష్ట గణనతో లెక్కించాలి. ఇది మొదట గందరగోళంగా ఉంది. కాబట్టి, కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

ఉదాహరణలు

అతిపెద్ద గ్రూప్ లీట్‌కోడ్ పరిష్కారాన్ని లెక్కించండి

n = 13
4

వివరణ: వాటి అంకెలు మొత్తం ప్రకారం సమూహం చేయబడిన సంఖ్యలు [1, 10], [2,11], [3,12], [4,13], [5], [6], [7], [ 8], [9]. కాబట్టి, గరిష్ట పౌన frequency పున్యం 4 కలిగిన 2 సమూహాలు ఉన్నాయి. అందువల్ల సమాధానం, 4.

n = 2
2

వివరణ: అదేవిధంగా, మీరు 2 వరకు సంఖ్యలను చూస్తే 2 సంఖ్యలు, 1 మరియు 2 మాత్రమే ఉన్నాయి. రెండూ ఒక్కొక్క సంఖ్యను కలిగి ఉన్న సమూహాన్ని సృష్టిస్తాయి. అందువల్ల సమాధానం 2 యొక్క గరిష్ట పౌన frequency పున్యాన్ని కలిగి ఉన్న 1 సమూహాలు.

అప్రోచ్

కౌంట్ లార్జెస్ట్ గ్రూప్ లీట్‌కోడ్ సొల్యూషన్ మాకు ఒకే పూర్ణాంకాన్ని అందించింది. మరియు గరిష్ట పౌన frequency పున్యాన్ని కలిగి ఉన్న సంఖ్యల సమూహాల సంఖ్యను లెక్కించమని అడిగారు, అక్కడ మేము వాటి సంఖ్యల సంఖ్య ప్రకారం సంఖ్యలను సమూహపరుస్తాము. ఇన్పుట్ గరిష్టంగా 10000 కు అడ్డంకి కాబట్టి. మేము ఒకదాన్ని సృష్టిస్తాము అమరిక సంఖ్యల అంకెలు మొత్తం యొక్క ఫ్రీక్వెన్సీని ఉంచడానికి. యొక్క గరిష్ట పరిమాణం cnt శ్రేణి 36 ఉండాలి. ఎందుకంటే గరిష్ట మొత్తంతో ఇన్‌పుట్ 36 అవుతుంది. కాబట్టి, 1 నుండి n వరకు ప్రతి సంఖ్యకు అంకెలు మొత్తాన్ని కనుగొనే విధానాన్ని మేము అనుకరిస్తాము. ఫ్రీక్వెన్సీ యొక్క మూల్యాంకనం సమయంలో, మేము ఇప్పటివరకు లెక్కించిన గరిష్ట పౌన frequency పున్యాన్ని నిల్వ చేస్తాము. ఇప్పుడు, మేము క్రొత్త లూప్‌ను ప్రారంభించి, గరిష్ట పౌన .పున్యం కలిగిన సమూహాల సంఖ్యను లెక్కించాము.

కౌంట్ అతిపెద్ద గ్రూప్ లీట్‌కోడ్ సొల్యూషన్ కోసం కోడ్

సి ++ కోడ్

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

int sumDigits(int n){
    int sum = 0;
    while(n>0){
        sum += (n%10);
        n /= 10;
    }
    return sum;
}

int countLargestGroup(int n) {
    int cnt[37];
    memset(cnt, 0, sizeof cnt);
    int mx = 0;
    for(int i=0;i<=n;i++){
        int s = sumDigits(i);
        cnt[s]++;
        if(cnt[s] > mx)
            mx = cnt[s];
    }
    
    int ans = 0;
    for(int i=0;i<37;i++){
        if(cnt[i] == mx)
            ans++;
    }
    return ans;
}

int main(){
    cout<<countLargestGroup(13);
}
4

జావా కోడ్

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static int sumDigits(int n){
        int sum = 0;
        while(n>0){
            sum += (n%10);
            n /= 10;
        }
        return sum;
    }

    public static int countLargestGroup(int n) {
        int cnt[] = new int[37];
        for(int i=0;i<37;i++)cnt[i] = 0;
        int mx = 0;
        for(int i=1;i<=n;i++){
            int s = sumDigits(i);
            cnt[s]++;
            if(cnt[s] > mx)
                mx = cnt[s];
        }

        int ans = 0;
        for(int i=0;i<37;i++){
            if(cnt[i] == mx)
                ans++;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.print(countLargetGroup(13));
    }
    
}
4

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

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

పై), ఎందుకంటే మొదటి లూప్ పరుగులు ఇన్‌పుట్‌పై ఆధారపడి ఉంటాయి. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

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

ఓ (1), మాకు స్థిరమైన పరిమాణ శ్రేణి ఉన్నందున. అందువల్ల ఇన్పుట్తో సంబంధం లేకుండా స్థలం సంక్లిష్టత స్థిరంగా ఉంటుంది.