විශාලතම කණ්ඩායම් ලීට්කෝඩ් විසඳුම ගණන් කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ මර්කාරි
අරා

ගණන් කිරීමේ සම්පූර්ණ කණ්ඩායම් ලීට්කෝඩ් විසඳුම අපට පූර්ණ සංඛ්‍යාවක් සපයයි. 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 ට බාධාවක් වන බැවින් අරාව ඉලක්කම්වල එකතුවෙහි සංඛ්‍යාතය තබා ගැනීමට. උපරිම ප්‍රමාණය cnt අරාව 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), පළමු ලූප් ධාවනය ආදානය මත රඳා පවතින බැවිනි. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපට නියත ප්‍රමාණයේ අරාවක් ඇති බැවින්. මේ අනුව ආදානය නොසලකා අවකාශයේ සංකීර්ණතාව නියතව පවතී.