Dado un número entero N , la tarea es encontrar el número de grupos que tienen el tamaño más grande. Cada número del 1 al N se agrupa según la suma de sus dígitos .
Ejemplos:
Entrada: N = 13
Salida: 4
Explicación:
Son 9 grupos en total, se agrupan según la suma de sus dígitos de números del 1 al 13: [1, 10] [2, 11] [3, 12] [ 4, 13] [5] [6] [7] [8] [9].
De estos, 4 grupos tienen el tamaño más grande que es 2.Entrada: n = 2
Salida: 2
Explicación:
Hay 2 grupos en total. [1] [2] y ambos grupos tienen el tamaño más grande 1.
Enfoque: Para resolver el problema mencionado anteriormente, necesitamos crear un diccionario cuya clave represente la suma única de los dígitos de los números del 1 al N. Los valores de esas claves llevarán la cuenta de cuántos números tienen la suma igual a su clave. Luego imprimiremos el valor más alto entre todos ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Count the
// number of groups having the largest
// size where groups are according
// to the sum of its digits
#include <bits/stdc++.h>
using namespace std;
// function to return sum of digits of i
int sumDigits(int n){
int sum = 0;
while(n)
{
sum += n%10;
n /= 10;
}
return sum;
}
// Create the dictionary of unique sum
map<int,int> constDict(int n){
// dictionary that contain
// unique sum count
map<int,int> d;
for(int i = 1; i < n + 1; ++i){
// calculate the sum of its digits
int sum1 = sumDigits(i);
if(d.find(sum1) == d.end())
d[sum1] = 1;
else
d[sum1] += 1;
}
return d;
}
// function to find the
// largest size of group
int countLargest(int n){
map<int,int> d = constDict(n);
int size = 0;
// count of largest size group
int count = 0;
for(auto it = d.begin(); it != d.end(); ++it){
int k = it->first;
int val = it->second;
if(val > size){
size = val;
count = 1;
}
else if(val == size)
count += 1;
}
return count;
}
// Driver code
int main()
{
int n = 13;
int group = countLargest(n);
cout << group << endl;
return 0;
}
Java
// Java implementation to Count the
// number of groups having the largest
// size where groups are according
// to the sum of its digits
import java.util.HashMap;
import java.util.Map;
class GFG{
// Function to return sum of digits of i
public static int sumDigits(int n)
{
int sum = 0;
while(n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
// Create the dictionary of unique sum
public static HashMap<Integer, Integer> constDict(int n)
{
// dictionary that contain
// unique sum count
HashMap<Integer, Integer> d = new HashMap<>();
for(int i = 1; i < n + 1; ++i)
{
// Calculate the sum of its digits
int sum1 = sumDigits(i);
if (!d.containsKey(sum1))
d.put(sum1, 1);
else
d.put(sum1, d.get(sum1) + 1);
}
return d;
}
// Function to find the
// largest size of group
public static int countLargest(int n)
{
HashMap<Integer, Integer> d = constDict(n);
int size = 0;
// Count of largest size group
int count = 0;
for(Map.Entry<Integer, Integer> it : d.entrySet())
{
int k = it.getKey();
int val = it.getValue();
if (val > size)
{
size = val;
count = 1;
}
else if (val == size)
count += 1;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int n = 13;
int group = countLargest(n);
System.out.println(group);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation to Count the
# number of groups having the largest
# size where groups are according
# to the sum of its digits
# Create the dictionary of unique sum
def constDict(n):
# dictionary that contain
# unique sum count
d ={}
for i in range(1, n + 1):
# convert each number to string
s = str(i)
# make list of number digits
l = list(s)
# calculate the sum of its digits
sum1 = sum(map(int, l))
if sum1 not in d:
d[sum1] = 1
else:
d[sum1] += 1
return d
# function to find the
# largest size of group
def countLargest(n):
d = constDict(n)
size = 0
# count of largest size group
count = 0
for k, val in d.items():
if val > size:
size = val
count = 1
elif val == size:
count += 1
return count
# Driver Code
n = 13
group = countLargest(n)
print(group)
# This code is contributed by Sanjit_Prasad
C#
// C# implementation to Count the
// number of groups having the largest
// size where groups are according
// to the sum of its digits
using System;
using System.Collections.Generic;
class GFG {
// Function to return sum of digits of i
static int sumDigits(int n)
{
int sum = 0;
while(n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
// Create the dictionary of unique sum
static Dictionary<int, int> constDict(int n)
{
// dictionary that contain
// unique sum count
Dictionary<int, int> d = new Dictionary<int, int>();
for(int i = 1; i < n + 1; ++i)
{
// Calculate the sum of its digits
int sum1 = sumDigits(i);
if (!d.ContainsKey(sum1))
d.Add(sum1, 1);
else
d[sum1] += 1;
}
return d;
}
// Function to find the
// largest size of group
static int countLargest(int n)
{
Dictionary<int, int> d = constDict(n);
int size = 0;
// Count of largest size group
int count = 0;
foreach(KeyValuePair<int, int> it in d)
{
int k = it.Key;
int val = it.Value;
if (val > size)
{
size = val;
count = 1;
}
else if (val == size)
count += 1;
}
return count;
}
// Driver code
static void Main()
{
int n = 13;
int group = countLargest(n);
Console.WriteLine(group);
}
}
// This code is contributed by divyesh072019
4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nishthagoel712 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA