[Leetcode] 1399. Count Largest Group

https://leetcode.com/problems/count-largest-group/description/?envType=daily-question&envId=2025-04-23

initial

easy q where i used dictionary but we can use dp later

btw we can use max(dic.values()) to get the maximum value of dictionary right away

class Solution:
    def countLargestGroup(self, n: int) -> int:
        dic={}
        for i in range(1,n+1):
            num = str(i)
            tmp=0
            tmp = sum(int(i) for i in num)
            if tmp not in dic:
                dic[tmp]=1
            else:
                dic[tmp]+=1
        maxVal=0
        ans=0
        print(dic)
        for i,v in dic.items():
            if v>maxVal:
                maxVal=v
                ans=1
            elif v==maxVal:
                ans+=1
            else:
                continue
        return ans

solution

notice we are recalculating previous standing numbers over and over again for long numbers. Lets say for example 125, 1+2 we has been already calculated for number 12 that came before 125. So we can store in our dp dic - key is number and value is the sum of that number. If there is that key, we can just add that value to the remaining number which in this case is 5.

Since dp is storing the sum of number, we need another data strcture to track the freq of that number so we can just use a list.

Also, max sum of number n=1~ 10^4 is 94. This is cuz when n=10, max is 9, n=100, max is 99, n=1000, max is 999. So it is just 94. Add a +1 just incase it goes out of boundary.

class Solution:
    def countLargestGroup(self, n: int) -> int:
        dp={0:0}
        lst = [0 for _ in range(4*9+1)]

        for i in range(1,n+1):
            quot,rem=divmod(i,10)
            dp[i]=dp[quot]+rem
            lst[dp[i]]+=1
        ans= lst.count(max(lst))
        return ans

complexity

o(n) time and space for dp