Given an integer n. Each number from 1 to n is grouped according to the sum of its digits. 
Return how many groups have the largest size.
 
Example 1:
Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.

Example 2:
Input: n = 2
Output: 2
Explanation: There are 2 groups [1], [2] of size 1.

Example 3:
Input: n = 15
Output: 6

Example 4:
Input: n = 24
Output: 5

 
Constraints:

1 <= n <= 10^4

Difficulty: introductory

Starter code:

class Solution:
    def countLargestGroup(self, n: int) -> int:
        

Solutions:
class Solution:
    memory = {}
    largest = [0]
    trackerForLargest = {}
    largestSize = [0]
    numGroups = [0]
    
    def countLargestGroup(self, n: int) -> int:
        if n > self.largest[0]:
            for num in range(self.largest[0] + 1, n + 1):
                curr = num
                currSum = 0
                while curr != 0:
                    currSum += curr%10
                    curr //= 10
                
                if currSum not in self.trackerForLargest:
                    self.trackerForLargest[currSum] = []
                
                self.trackerForLargest[currSum].append(num)
                
                if len(self.trackerForLargest[currSum]) == self.largestSize[0]:
                    self.numGroups[0] += 1
                elif len(self.trackerForLargest[currSum]) > self.largestSize[0]:
                    self.numGroups[0] = 1
                    self.largestSize[0] = len(self.trackerForLargest[currSum])
                
                self.memory[num] = self.numGroups[0]
            
            self.largest[0] = n
        
        return self.memory[n]

class Solution:
    def countLargestGroup(self, n: int) -> int:
        if n < 10:
            return n
        counter = [0]*37
        sumCount = {0:0}
        i = 1
        while i <= n:
            quotient, reminder = divmod(i, 10)
            sumCount[i] = reminder + sumCount[quotient]
            counter[sumCount[i]] += 1
            i += 1
        return counter.count(max(counter))

class Solution:
    def countLargestGroup(self, n: int) -> int:
        dic = {}
        for i in range(1, n + 1):
            key = 0
            while i:
                key += i % 10
                i = i // 10
            dic[key] = dic.get(key, 0) + 1
        
        size = list(dic.values())
        return size.count(max(size))

class Solution:
    def countLargestGroup(self, n: int) -> int:
        def sum_num(n):
            res = n % 10
            while n > 0:
                res += (n := n // 10) % 10
            
            return res
        
        
        groups = defaultdict(int)
        for i in range(1, n + 1):
            groups[sum_num(i)] += 1
            
        high = max(groups.values())
        return sum(1 for v in groups.values() if v == high)

class Solution:
    def countLargestGroup(self, n: int) -> int:
        
        counts = {}
        m = 0
        
        for i in range(1, n+1):
            t = i
            s = 0
            while t:
                s += t % 10
                t //= 10
                
            counts[s] = counts.setdefault(s, 0) + 1
            if m < counts[s]:
                m = counts[s]
            
        return sum(v == m for v in list(counts.values()))
                


class Solution:
    def countLargestGroup(self, n: int) -> int:
        
        groups = [0]
        
        for i in range(1, n+1, 1):
            sumDigi = self.sumOfDigits(i)
            if (sumDigi == len(groups)):
                groups.append(0)
            groups[sumDigi]+=1            
        #print(groups)
        
        
        
        maxGroup = 0
        maxCount = 0
        for grp in groups:
            if (grp > maxGroup):
                maxGroup = grp
                maxCount = 0
            if (grp == maxGroup):
                maxCount += 1
        #print(\"maxGroup=%d, maxCount=%d\" % (maxGroup, maxCount))
                
        return maxCount
        
        
        
    def sumOfDigits(self, n:int) -> int:
        sum = 0
        while (n>0):
            sum += n%10
            n //= 10
        return sum

class Solution:
    def countLargestGroup(self, n: int) -> int:
        def countDigits(m):
            res = 0
            while m > 0:
                res += m % 10
                m //= 10
            return res
        dic = collections.defaultdict(list)
        for i in range(1,n+1):
            count_i = countDigits(i)
            dic[count_i].append(i)
        
        max_count = max(len(dic[k]) for k in dic)
        res = [len(dic[k])==max_count for k in dic]
        return sum(res)
            


class Solution:
    def countLargestGroup(self, n: int) -> int:
        d={};
        for i in range(1,n+1):
            sum=0;
            s=str(i);
            for c in s:
                sum+=int(c);
            if sum in d:
                d[sum].append(i);
            else:
                d[sum]=[i];
        values=list(d.values());
        values.sort(key=len,reverse=True);
        
        count=0;
        length=len(values[0]);
        for v in values:
            if length==len(v):
                count+=1;
        return count;


class Solution:
    def countLargestGroup(self, n: int) -> int:
        arr = [0]*36
        
        for i in range(1,n+1):
            sm = 0
            for j in str(i):
                sm += int(j)
            arr[sm-1]+=1
        
        count = 0
        
        mx = max(arr)
        
        for i in arr:
            if i == mx:
                count+=1
        
        return count


import collections

class Solution:
    def countLargestGroup(self, n: int) -> int:
        digit_dict = collections.defaultdict(list)
        max_curr = 0
        answer = 0
        
        def get_digit_sum(num):
            return sum(map(int, str(num)))
        
        for i in range(1, n+1):
            digit_sum_curr = get_digit_sum(i)
            digit_dict[digit_sum_curr].append(i)
            
            if len(digit_dict[digit_sum_curr]) > max_curr:
                max_curr = len(digit_dict[digit_sum_curr]) 
                answer = 1
            elif len(digit_dict[digit_sum_curr]) == max_curr:
                answer += 1
                
        return answer
            


class Solution:
    def countLargestGroup(self, n: int) -> int:
        dic = defaultdict(list)
        max_ = 0
        for i in range(1,n+1):
            result = 0
            num = i
            while i > 0:
                rem = i % 10
                result += rem
                i = int(i/10)

            dic[result].append(num)
            #max_ = max(max_, len(dic[result]))
                
        max_ = 0
        for i in dic:
            leng = len(dic[i])
            max_ = max(max_, leng)
            
        
        ans = [dic[key] for key in dic if len(dic[key])==max_]
        #ans = 0
        #for i in list(dic.values()):
         #   if len(i)==max_:
          #      ans+=1
        #return ans
        return len(ans)
            
                    
                   
   


class Solution:
    def countLargestGroup(self, n: int) -> int:
        groups = {}
        max = 0
        for i in range(1,n+1):
            num_str = str(i)
            sum = 0
            for x in num_str:
                sum += int(x)
            if sum in groups:
                groups[sum].append(n)
            else:
                groups[sum] = [n]
            
            max = max if len(groups[sum])< max else len(groups[sum])
        
        num_groups = 0
        for g in groups:
            if len(groups[g]) == max:
                num_groups += 1
                
        return num_groups

class Solution:
    def countLargestGroup(self, n: int) -> int:
        dp = {0:0}
        counts = [0]*36
        for i in range(1,n+1):
            a, b = divmod(i,10)
            dp[i] = b+dp[a]
            counts[dp[i]-1]+=1
        return counts.count(max(counts))
        
        


class Solution:
    def countLargestGroup(self, n: int) -> int:
        dic = {}
        for i in range(1, n+1):
            summed = sum([int(k) for k in str(i)])
            if(summed in dic):
                dic[summed].append(i)
            else:
                dic[summed] = [i]
        maximumLen = max([len(value) for value in dic.values()])
        count = 0
        for value in dic.values():
            if(len(value) == maximumLen):
                count += 1
        return count

class Solution:
    def countLargestGroup(self, n: int) -> int:
        sum_to_nums = {}
        for i in range(1,n+1):
            digit_sum = self.getDigitSum(i)
            if digit_sum in sum_to_nums:
                sum_to_nums[digit_sum].append(i)
            else:
                sum_to_nums[digit_sum] = [i]
        print(sum_to_nums)
        values = list(sum_to_nums.values())
        
        num_values = list([len(v) for v in values]) 
        largest_group = max(num_values)
        print(num_values)
        #find how many 
        summing = [1 if x==largest_group else 0 for x in num_values]
        print(summing)
        return sum(summing)
        
            
            
    def getDigitSum(self, num):
        #print(\"getting sum of digits in\", num)
        sum_so_far = 0
        while num != 0:
            digit = num%10
            sum_so_far = sum_so_far + digit
            num = int(num/10)
        
        #print(sum_so_far)
        return sum_so_far
        
            


class Solution:
    def countLargestGroup(self, n: int) -> int:
        l = [0]*40
        for i in range(1,n+1):
            s = str(i)
            sum = 0
            for j in range(len(s)):
                sum+=int(s[j])
            # print(sum)
            l[sum]+=1
        mm =  max(l)
        c = 0
        for i in range(len(l)):
            if(l[i]==mm):
                c+=1
        return c


class Solution:
    def sumByDigits(self, num: int) -> int:
        result, _n = 0, num
        while _n > 0:
            result += _n % 10
            _n = math.floor(_n / 10)
        return result
    
    def countLargestGroup(self, n: int) -> int:        
        counter = collections.defaultdict(int)
        max_value = 0
        result = 0
        for i in range(1, n + 1):
            key = self.sumByDigits(i)
            counter[key] += 1
            if counter[key] > max_value:
                max_value = counter[key]
                result = 1
            elif counter[key] == max_value:
                result += 1
        return result

class Solution:
    def countLargestGroup(self, n: int) -> int:
        sums = {}
        max_len = 0
        for num in range(1, n + 1):
            digits = str(num)
            sum = 0
            if len(digits) > max_len:
                max_len = len(digits)
            for char in digits:
                sum = sum + int(char)
            
            arr = [sum, num]
            
            arr = [sum, num]
            
            if sum in sums:
                sums[sum].extend([arr])
            else:
                sums[sum] = [arr]
        
        sorted_sums = sorted(sums, reverse=True, key = lambda x: len(sums.get(x)))
        max_len = len(sums.get(sorted_sums[0]))
        count = 0
        for key in sorted_sums:
            items = sums.get(key)
            if len(items) != max_len:
                break
            else:
                count = count + 1
        
        return count

class Solution:
    def countLargestGroup(self, n: int) -> int:
        from collections import Counter
        al = [list(str(i)) for i in range(1,n+1)]
        al = [sum([int(j) for j in i]) for i in al]
        col = Counter(al)
        #print(col)
        num = Counter(col.values())
        #print(num)
        return num[max(num.keys(),key=lambda x:x)]

class Solution:
    def countLargestGroup(self, n: int) -> int:
        nums = {}
        for i in range(1, n+1):
            total = sum(list([int(x) for x in str(i)]))
            nums[total] = 1 if total not in nums else 1 + nums[total]
        maxCount = max(nums.values())
        return list(nums.values()).count(maxCount)


class Solution:
    def countLargestGroup(self, n: int) -> int:
        nums = {}
        for i in range(1, n+1):
            total = sum(list([int(x) for x in str(i)]))
            nums[total] = 1 + nums.get(total, 0)
        maxCount = max(nums.values())
        return list(nums.values()).count(maxCount)


class Solution:
    def countLargestGroup(self, n: int) -> int:
        
        if(n == 2):
            return 2
        
        mix = {}
        
        for i in range(1, n + 1):
            if dsum(i) not in mix:
                mix[dsum(i)] = [i]
            else:
                mix[dsum(i)].append(i)
        
        mx = 0
        for i in list(mix.values()):
            if( len(i) > mx ):
                mx = len(i)
                
        resc = 0
        for i in list(mix.values()):
            if( len(i) == mx ):
                resc = resc + 1
                
        return resc
            
def dsum(digit):
    cnt = 0
    while(digit > 0):
        temp = digit % 10
        cnt = cnt + temp
        digit = digit // 10
        
    return cnt


class Solution:
    def countLargestGroup(self, n: int) -> int:
        nums = {}
        maxFreq = 1
        maxCount = 0
        for i in range(1, n + 1):
            total = sum(list([int(x) for x in str(i)]))
            nums[total] = 1 + nums.get(total, 0)
            if nums[total] > maxFreq:
                maxFreq = nums[total]
                maxCount = 1
            elif nums[total] == maxFreq:
                maxCount += 1
        return maxCount


class Solution:
    def countLargestGroup(self, n: int) -> int:
        dp = {0:0}
        counter = [0]*37 # 9999 digitsum is 36
        for num in range(1, n+1):
            div, mod = divmod(num, 10)
            dp[num] = dp[div]+mod
            counter[dp[num]] += 1
        return counter.count(max(counter))

class Solution:
    def countLargestGroup(self, n: int) -> int:
        print(n)
        str_nums = [str(i) for i in range(1, n + 1)]
        print(str_nums)
        digits = [ [int(i) for i in s] for s in str_nums]
        print(digits)
        sums = [sum(i) for i in digits]
        print(sums)
        group_sizes = {}
        for s in sums:
            group_sizes[s] = group_sizes.get(s, 0) + 1
        max_size = max(group_sizes.values())
        return len([i for i in group_sizes if group_sizes[i] == max_size])


class Solution:
    def countLargestGroup(self, n: int) -> int:
        nums = collections.defaultdict(int)
        maxFreq = 1
        maxCount = 0
        for i in range(1, n + 1):
            total = sum(list([int(x) for x in str(i)]))
            nums[total] = 1 + nums.get(total, 0)
            if nums[total] > maxFreq:
                maxFreq = nums[total]
                maxCount = 1
            elif nums[total] == maxFreq:
                maxCount += 1
        return maxCount


class Solution:
    def countLargestGroup(self, n: int) -> int:
        if n<10:
            return n
        arr=[[1],[2],[3],[4],[5],[6],[7],[8],[9]]
        for i in range(10,n+1):
            k=list(map(int,list(str(i))))
            k=sum(k)
            print(k)
            if k<=len(arr):
                arr[k-1].append(i)
            else:
                arr.append([k])
        arr=sorted(arr, key=len,reverse=True)
        print(arr)
        l=len(arr[0])
        i=0
        while i<len(arr) and len(arr[i])==l:
            i+=1
        return i

def sum_of_digits(num):
    total = 0
    while num > 0:
        total += num % 10
        num //= 10
    return total

class Solution:
    def countLargestGroup(self, n: int) -> int:
        groups = {}
        for i in range(1, n + 1):
            s = sum_of_digits(i)
            groups[s] = groups.get(s, []) + [i]
        max_len = 0
        for lst in groups.values():
            max_len = max(max_len, len(lst))
        largest = 0
        for lst in groups.values():
            if len(lst) == max_len: largest += 1
        return largest

class Solution:
    def countLargestGroup(self, n: int) -> int:
        numsum = lambda x: sum(map(int, list(str(x))))
        numdict = {}
        maxcount = 0
        
        for i in range(1, n+1):
            x = numsum(i)
            numdict[x] = numdict.get(x, 0) + 1
            maxcount = max(maxcount, numdict[x])
        
        count = 0
        for i in numdict:
            if numdict[i] == maxcount:
                count += 1
        
        return count


import collections

class Solution:
    def countLargestGroup(self, n: int) -> int:
        digit_dict = collections.defaultdict(list)
        max_curr = 0
        answer = 0
        
        def get_digit_sum(num):
            return sum(int(i) for i in [char for char in str(num)])
        
        for i in range(1, n+1):
            digit_sum_curr = get_digit_sum(i)
            digit_dict[digit_sum_curr].append(i)
            
            if len(digit_dict[digit_sum_curr]) > max_curr:
                max_curr = len(digit_dict[digit_sum_curr]) 
                answer = 1
            elif len(digit_dict[digit_sum_curr]) == max_curr:
                answer += 1
                
        return answer
            


class Solution:
    def countLargestGroup(self, n: int) -> int:
        q=[]
        for i in range(n-10+1):
            q.append(i + 10)
            
        l=[]
           
        for j in range(len(q)):
            p=0
            for k in range(len(str(q[j]))):
                #print(str(q[j])[k])
                p=p+int(str(q[j])[k])
            l.append(p)
        #print(l)
        q=Counter(l)
        x=0
        
        print(q)
        
        for j,i in list(q.items()):
            if j <10:
                
                q[j]=q[j]+1
            
        print(q)   
        for j,i in list(q.items()):
            
            if i == max(q.values()):
                x= x+1
        if n < 10:
            return n
            #print(n)
        else:
            return (x)
            #print(x)
            
        
        
        
            
                
                    
                    
    


class Solution:
    def countLargestGroup(self, n: int) -> int:
        def sumDigits(n):
            if n < 10: return n
            sum = 0
            while n:
                sum += n % 10
                n //= 10
            return sum
        cnt = [0 for i in range(37)] 
        max_size, max_cnt = 0, 0
        while n:
            cnt[sumDigits(n)] += 1
            if max_size < cnt[sumDigits(n)]:
                max_size = cnt[sumDigits(n)]
                max_cnt = 1
            else:
                max_cnt += max_size == cnt[sumDigits(n)]
            n -= 1
        return max_cnt    

class Solution:
    def countLargestGroup(self, n: int) -> int:
        d, c = {}, 0
        for i in range(1, n+1):
            if i % 10 == 0:
                c = sum(map(int, str(i)))
                d[c] = d.get(c, 0) + 1
            else:
                c += 1
                d[c] = d.get(c, 0) + 1
        res, m = 0, 0
        for v in list(d.values()):
            if v > m:
                res = 1
                m = v
            elif v == m:
                res += 1
        return res
    


class Solution:
    def countLargestGroup(self, n: int) -> int:
        d = {}
        for num in range(1, n+1):
            sumn = 0
            for char in str(num):
                sumn += int(char)
            d[sumn] = d[sumn] + [num] if sumn in d else [num]
        t = {}
        for arr in d.values():
            t[len(arr)] = t[len(arr)] + 1 if len(arr) in t else 1
        tt = sorted(t, reverse=True)
        return t[next(iter(tt))]

class Solution:
    def countLargestGroup(self, n: int) -> int:
        map = {}
        mx = 0
        for i in range(1, n+1):
            tempSum = 0
            for j in str(i):
                tempSum += int(j)
            map[tempSum] = map.get(tempSum, []) + [i]
            mx = max(mx, len(map.get(tempSum)))
        res = 0
        for key in map.keys():
            if len(map.get(key)) == mx:
                res += 1
        return res

class Solution:
    def countLargestGroup(self, n: int) -> int:
        dic = {}
        for i in range(1,n+1):
            s = sum([int(i) for i in str(i)])
            if s in dic:
                dic[s].append(i)
            else:
                dic[s] = [i]
             
        max_L = 0
        cnt = 0
        for j in dic:
            if len(dic[j]) == max_L:
                cnt += 1
            elif len(dic[j]) > max_L:
                cnt = 1
                max_L = len(dic[j])
                
        return cnt


class Solution:
    def countLargestGroup(self, n: int) -> int:
        num_dict = {}
        for i in range(1, n+1):
            arr = [int(a) for a in str(i)]
            summa = sum(arr)
            if summa not in num_dict.keys():
                num_dict[summa] = [i]
            else:
                num_dict[summa] = num_dict[summa] + [i]
        large = 0
        for j in num_dict.values():
            if len(j)>large:
                large = len(j)
        count = 0
        for j in num_dict.values():
            if len(j) == large:
                count += 1
        return count

class Solution:
    def countLargestGroup(self, n: int) -> int:
        d = {}
        for i in range(1, n+1):
            s = sum([int(x) for x in str(i)])
            d[s] = d.get(s, []) + [i]
        nums = [len(d[x]) for x in d]
        d = collections.Counter(nums)
        return d[max(nums)]



class Solution:
    def countLargestGroup(self, n: int) -> int:
        dp = {0: 0}
        counts = [0] * (4 * 9)
        for i in range(1, n + 1):
            quotient, reminder = divmod(i, 10)
            dp[i] = reminder + dp[quotient]
            counts[dp[i] - 1] += 1
        return counts.count(max(counts))

class Solution:
    def countLargestGroup(self, n: int) -> int:
        groups = [0]*37
        for i in range(1,n+1):
            t,i = divmod(i,1000)
            h,i = divmod(i,100)
            ten,i = divmod(i,10)
            groups[t + h + ten + i] += 1
        max = 0
        count = 0
        for g in groups:
            if g > max:
                max = g
                count = 1
            elif g == max:
                count += 1                
        return count
            
        


class Solution:
    def countLargestGroup(self, n: int) -> int:
        memo = {1: 1}
        
        for i in range(2, n + 1):
            if not i % 10:
                memo[i] = memo[i // 10]
            else:
                memo[i] = memo[i - 1] + 1
        D = defaultdict(int)
        for k, v in memo.items():
            D[v] += 1
        res = 0
        
        for k in D.keys():
            if D[k] == max(D.values()):
                res += 1
        return res