Blogs Hub

Count Largest Group - Array - Easy - LeetCode - MiniTV

Count Largest Group - Array - Easy - LeetCode - मिनी टीवी

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

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class CountLargestGroupSoln
    {
        public int CountLargestGroup(int n)
        {
            var dict = new Dictionary<int, int>();
            int sum = 0;
            int max = int.MinValue;
            for(int i = 1; i <= n; i++)
            {
                sum = FindSum(i);
                if (dict.ContainsKey(sum))
                {
                    dict[sum]++;
                }
                else
                {
                    dict.Add(sum, 1);
                }

                if (max < dict[sum])
                {
                    max = dict[sum];
                }
            }

            int count = 0;
            foreach (var item in dict)
            {
                if (max == item.Value)
                {
                    count++;
                }
            }

            return count;
        }

        private int FindSum(int i)
        {            
            int sum=0;
            while (i > 0)
            {
                sum += i % 10;
                i = i / 10;
            }

            return sum;
        }
    }
}

 

Time Complexity: O(n)

Space Complexity: O(1)

 

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
    [TestClass]
    public class CountLargestGroupSolnTests
    {
        [TestMethod]
        public void CountLargestGroupSoln_First()
        {
            var n = 13;
            var output = 4;
            var res = new CountLargestGroupSoln().CountLargestGroup(n);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void CountLargestGroupSoln_Second()
        {
            var n = 2;
            var output = 2;
            var res = new CountLargestGroupSoln().CountLargestGroup(n);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void CountLargestGroupSoln_Third()
        {
            var n = 15;
            var output = 6;
            var res = new CountLargestGroupSoln().CountLargestGroup(n);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void CountLargestGroupSoln_Fourth()
        {
            var n = 24;
            var output = 5;
            var res = new CountLargestGroupSoln().CountLargestGroup(n);

            Assert.AreEqual(res, output);
        }
    }
}