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);
}
}
}
