ഏറ്റവും വലിയ ഗ്രൂപ്പ് ലീറ്റ്കോഡ് പരിഹാരം എണ്ണുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു മെർക്കാരി
അറേ

ക Count ണ്ട് കംപ്ലീറ്റ് ഗ്രൂപ്പ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ ഞങ്ങൾക്ക് ഒരു സംഖ്യ നൽകുന്നു. 1 നും n നും ഇടയിലുള്ള ഓരോ സംഖ്യയുടെയും അക്കങ്ങളുടെ ആകെത്തുക ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട് (ഉൾപ്പെടെ). അതിനുശേഷം ഞങ്ങൾ അക്കങ്ങളുടെ അതേ സംഖ്യകളോടെ ഗ്രൂപ്പുചെയ്യുകയും ഒരു എണ്ണം സൂക്ഷിക്കുകയും ചെയ്യും. ഗ്രൂപ്പുകളുടെ എണ്ണം പരമാവധി എണ്ണിക്കൊണ്ട് ഞങ്ങൾ കണക്കാക്കേണ്ടതുണ്ട്. ഇത് ആദ്യം ആശയക്കുഴപ്പത്തിലാണെന്ന് തോന്നുന്നു. അതിനാൽ, കുറച്ച് ഉദാഹരണങ്ങൾ നോക്കാം.

ഉദാഹരണങ്ങൾ

ഏറ്റവും വലിയ ഗ്രൂപ്പ് ലീറ്റ്കോഡ് പരിഹാരം എണ്ണുക

n = 13
4

വിശദീകരണം: അവയുടെ അക്കങ്ങളുടെ ആകെത്തുക പ്രകാരം ഗ്രൂപ്പുചെയ്‌ത അക്കങ്ങൾ [1, 10], [2,11], [3,12], [4,13], [5], [6], [7], [ 8], [9]. അതിനാൽ, പരമാവധി ആവൃത്തി 4 ഉള്ള 2 ഗ്രൂപ്പുകളുണ്ട്. അതിനാൽ ഉത്തരം, 4.

n = 2
2

വിശദീകരണം: അതുപോലെ, നിങ്ങൾ 2 വരെ അക്കങ്ങൾ കാണുകയാണെങ്കിൽ, 2, 1, 2 എന്നിവ മാത്രമേയുള്ളൂ. രണ്ടും ഒരു സംഖ്യ വീതമുള്ള ഒരു ഗ്രൂപ്പ് സൃഷ്ടിക്കുന്നു. അങ്ങനെ പരമാവധി 2 ആവൃത്തിയിലുള്ള 1 ഗ്രൂപ്പുകളാണ് ഉത്തരം.

സമീപനം

ഏറ്റവും വലിയ ഗ്രൂപ്പ് ലീറ്റ്കോഡ് പരിഹാരം എണ്ണുക എന്ന പ്രശ്നം ഞങ്ങൾക്ക് ഒരു പൂർണ്ണസംഖ്യ നൽകി. പരമാവധി ആവൃത്തിയിലുള്ള അക്കങ്ങളുടെ ഗ്രൂപ്പുകളുടെ എണ്ണം കണക്കാക്കാൻ ആവശ്യപ്പെടുകയും അക്കങ്ങളുടെ ആകെത്തുക അനുസരിച്ച് ഞങ്ങൾ അക്കങ്ങൾ ഗ്രൂപ്പുചെയ്യുകയും ചെയ്യുന്നു. ഇൻപുട്ട് പരമാവധി 10000 എന്ന പരിമിതിയായതിനാൽ. ഞങ്ങൾ ഒരു സൃഷ്ടിക്കുന്നു ശ്രേണി അക്കങ്ങളുടെ ആകെത്തുകയുടെ ആവൃത്തി നിലനിർത്താൻ. ന്റെ പരമാവധി വലുപ്പം കറ്റലോണിയയിലെ അറേ 36 ആയിരിക്കണം. കാരണം പരമാവധി സംഖ്യയുള്ള ഇൻപുട്ട് 36 ആയിരിക്കും. അതിനാൽ, 1 മുതൽ n വരെയുള്ള ഓരോ സംഖ്യയുടെയും അക്കങ്ങളുടെ ആകെത്തുക കണ്ടെത്തുന്ന പ്രക്രിയ ഞങ്ങൾ അനുകരിക്കുന്നു. ആവൃത്തിയുടെ മൂല്യനിർണ്ണയ സമയത്ത്, ഇപ്പോൾ വരെ കണക്കാക്കിയ പരമാവധി ആവൃത്തി ഞങ്ങൾ സംഭരിക്കുന്നു. ഇപ്പോൾ, ഞങ്ങൾ ഒരു പുതിയ ലൂപ്പ് ആരംഭിച്ച് പരമാവധി ആവൃത്തിയിലുള്ള ഗ്രൂപ്പുകളുടെ എണ്ണം കണക്കാക്കുന്നു.

ഏറ്റവും വലിയ ഗ്രൂപ്പ് ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള കോഡ്

സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ആദ്യത്തെ ലൂപ്പ് റൺസ് ഇൻപുട്ടിനെ ആശ്രയിച്ചിരിക്കുന്നു. അങ്ങനെ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), ഞങ്ങൾക്ക് സ്ഥിരമായ വലുപ്പ അറേ ഉള്ളതിനാൽ. ഇൻപുട്ട് പരിഗണിക്കാതെ തന്നെ സ്പേസ് സങ്കീർണ്ണത സ്ഥിരമായി തുടരുന്നു.