Dada una array de números naturales hasta N y dos números M y K , la tarea es encontrar la suma de M números máximos de suma de dígitos distintos M de N números naturales que son factores de K .
Ejemplos:
Entrada: N = 50, M = 4, K = 30
Salida: 16
Explicación:
De 1 a 50, factores de 30 = {1, 2, 3, 5, 6, 10, 15, 30}.
Suma de dígitos de cada factor = {1, 2, 3, 5, 6, 1, 6, 3}.
Suma de los 4 dígitos más grandes = 2, 3, 5, 6.
Suma = 16Entrada: N = 5, M = 3, K = 74
Salida: 3
Explicación:
De 1 a 5 factores de 74 = {1, 2}
Suma de dígitos de cada factor = {1, 2}.
La suma de los 3 dígitos más grandes = 1, 2 (Aquí solo están presentes 2 de estos números. Pero se solicita como máximo M. Por lo tanto, solo se considerarán estos 2).
Suma = 3
Enfoque ingenuo: la solución simple es ejecutar el ciclo de 1 a N y encontrar la lista de todos los números que divide perfectamente a K. Encuentre la suma de dígitos de cada factor y ordénelos en orden descendente e imprima M elementos distintos de esta lista desde arriba.
Enfoque eficiente:
- Encuentre todos los factores de K en el rango de 1 a N iterando de 2 a √K de modo que el elemento divida completamente el número. Para obtener una explicación detallada de este enfoque, consulte este artículo y guárdelos en una array.
- Encuentre la suma de dígitos de los números almacenados en la array de factores.
Por ejemplo:
For the Given Array - {4, 10, 273 }
Digit Sum of the Elements -
Element 0 Digit Sum - "4" = 4
Element 1 Digit Sum - "10" = 1 + 0 = 10
Element 2 Digit Sum - "273" = 2 + 7 + 3 = 12
- Elimine los duplicados de la suma de dígitos ya que necesitamos elementos distintos.
- Ordene las distintas sumas de dígitos en orden inverso y encuentre la suma de los primeros M elementos como máximo de esta array de suma de dígitos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to find the sum of
// maximum distinct digit sum of at most
// M numbers from 1 to N that are factors of K
#include <bits/stdc++.h>
using namespace std;
// Function to find the factors
// of K in N
vector<int> findFactors(int n, int k)
{
// Initialise a vector
vector<int> factors;
// Find out the factors of
// K less than N
for (int i = 1; i <= sqrt(k); i++) {
if (k % i == 0) {
if (k / i == i && i <= n)
factors.push_back(i);
else {
if (i <= n)
factors.push_back(i);
if (k / i <= n)
factors.push_back(k / i);
}
}
}
return factors;
}
// Find the digit sum of each factor
vector<int> findDigitSum(vector<int> a)
{
// Sum of digits for each
// element in vector
for (int i = 0; i < a.size(); i++) {
int c = 0;
while (a[i] > 0) {
c += a[i] % 10;
a[i] = a[i] / 10;
}
a[i] = c;
}
return a;
}
// Find the largest M distinct digit
// sum from the digitSum vector
int findMMaxDistinctDigitSum(
vector<int> distinctDigitSum,
int m)
{
// Find the sum of last M numbers.
int sum = 0;
for (int i = distinctDigitSum.size() - 1;
i >= 0 && m > 0;
i--, m--)
sum += distinctDigitSum[i];
return sum;
}
// Find the at most M numbers from N natural
// numbers whose digit sum is distinct
// and those M numbers are factors of K.
int findDistinctMnumbers(int n, int k, int m)
{
// Find out the factors of
// K less than N
vector<int> factors = findFactors(n, k);
// Sum of digits for each
// element in vector
vector<int> digitSum = findDigitSum(factors);
// Sorting the digitSum vector
sort(digitSum.begin(), digitSum.end());
// Removing the duplicate elements
vector<int>::iterator ip;
ip = unique(digitSum.begin(), digitSum.end());
digitSum.resize(distance(
digitSum.begin(),
ip));
// Finding the sum and returning it
return findMMaxDistinctDigitSum(digitSum, m);
}
// Driver Code
int main()
{
int n = 100, k = 80, m = 4;
// Function Call
cout
<< findDistinctMnumbers(n, k, m)
<< endl;
return 0;
}
Java
// Java implementation to find the sum of
// maximum distinct digit sum of at most
// M numbers from 1 to N that are factors of K
import java.util.*;
class GFG
{
// Function to find the factors
// of K in N
public static Vector<Integer> findFactors(int n, int k)
{
Vector<Integer> factors = new Vector<Integer>();
// Initialise a vector
// Find out the factors of
// K less than N
for (int i = 1; i <= Math.sqrt(k); i++)
{
if (k % i == 0)
{
if (k / i == i && i <= n)
factors.add(i);
else
{
if (i <= n)
factors.add(i);
if (k / i <= n)
factors.add(k / i);
}
}
}
return factors;
}
// Find the digit sum of each factor
public static Vector<Integer> findDigitSum(Vector<Integer> a)
{
// Sum of digits for each
// element in vector
for (int i = 0; i < a.size(); i++)
{
int c = 0;
while (a.get(i) > 0)
{
c += (a.get(i) % 10);
a.set(i,(a.get(i)/10));
}
a.set(i,c);
}
return a;
}
// Find the largest M distinct digit
// sum from the digitSum vector
public static int findMMaxDistinctDigitSum(Vector<Integer> distinctDigitSum,int m)
{
// Find the sum of last M numbers.
int sum = 0;
for (int i = distinctDigitSum.size() - 1;
i >= 0 && m > 0;i--, m--)
sum += distinctDigitSum.get(i);
return sum;
}
// Find the at most M numbers from N natural
// numbers whose digit sum is distinct
// and those M numbers are factors of K.
public static int findDistinctMnumbers(int n, int k, int m)
{
// Find out the factors of
// K less than N
Vector<Integer> factors = findFactors(n, k);
// Sum of digits for each
// element in vector
Vector<Integer> digitSum = findDigitSum(factors);
// Sorting the digitSum vector
Collections.sort(digitSum);
// Removing the duplicate elements
HashSet<Integer> hs1 = new HashSet<Integer>(digitSum);
//"HashSet" is stores only unique elements
Vector<Integer> vect2 = new Vector<Integer>(hs1);
// Finding the sum and returning it
return findMMaxDistinctDigitSum(vect2, m);
}
// Driver Code
public static void main(String args[])
{
int n = 100, k = 80, m = 4;
// Function Call
System.out.println(findDistinctMnumbers(n, k, m));
}
}
// This code is contributed by SoumikMondal
Python3
# Python 3 implementation to find the sum of # maximum distinct digit sum of at most # M numbers from 1 to N that are factors of K import math # Function to find the factors # of K in N def findFactors(n, k): # Initialise a vector factors = [] # Find out the factors of # K less than N sqt = (int)(math.sqrt(k)) for i in range(1, sqt): if (k % i == 0): if (k // i == i and i <= n): factors.append(i) else: if (i <= n): factors.append(i) if (k // i <= n): factors.append(k // i) return factors # Find the digit sum of each factor def findDigitSum(a): # Sum of digits for each # element in vector for i in range(len(a)): c = 0 while (a[i] > 0): c += a[i] % 10 a[i] = a[i] // 10 a[i] = c return a # Find the largest M distinct digit # sum from the digitSum vector def findMMaxDistinctDigitSum( distinctDigitSum, m): # Find the sum of last M numbers. sum = 0 i = len(distinctDigitSum) - 1 while (i >= 0 and m > 0): sum += distinctDigitSum[i] i -= 1 m -= 1 return sum # Find the at most M numbers from N natural # numbers whose digit sum is distinct # and those M numbers are factors of K def findDistinctMnumbers(n, k, m): # Find out the factors of # K less than N factors = findFactors(n, k) # Sum of digits for each # element in vector digitSum = findDigitSum(factors) # Sorting the digitSum vector digitSum.sort() # Removing the duplicate elements ip = list(set(digitSum)) # Finding the sum and returning it return findMMaxDistinctDigitSum(ip, m) # Driver Code if __name__ == "__main__": n = 100 k = 80 m = 4 # Function Call print(findDistinctMnumbers(n, k, m)) # This code is contributed by chitranayal
Javascript
<script>
// Javascript implementation to find the sum of
// maximum distinct digit sum of at most
// M numbers from 1 to N that are factors of K
// Function to find the factors
// of K in N
function findFactors(n, k)
{
let factors = [];
// Initialise a vector
// Find out the factors of
// K less than N
for(let i = 1; i <= Math.sqrt(k); i++)
{
if (k % i == 0)
{
if (k / i == i && i <= n)
factors.push(i);
else
{
if (i <= n)
factors.push(i);
if (k / i <= n)
factors.push(k / i);
}
}
}
return factors;
}
// Find the digit sum of each factor
function findDigitSum(a)
{
// Sum of digits for each
// element in vector
for(let i = 0; i < a.length; i++)
{
let c = 0;
while (a[i] > 0)
{
c += (a[i] % 10);
a[i] = Math.floor(a[i] / 10);
}
a[i] = c;
}
return a;
}
// Find the largest M distinct digit
// sum from the digitSum vector
function findMMaxDistinctDigitSum(distinctDigitSum, m)
{
// Find the sum of last M numbers.
let sum = 0;
for(let i = distinctDigitSum.length - 1;
i >= 0 && m > 0;i--, m--)
sum += distinctDigitSum[i];
return sum;
}
// Find the at most M numbers from N natural
// numbers whose digit sum is distinct
// and those M numbers are factors of K.
function findDistinctMnumbers(n, k, m)
{
// Find out the factors of
// K less than N
let factors = findFactors(n, k);
// Sum of digits for each
// element in vector
let digitSum = findDigitSum(factors);
// Sorting the digitSum vector
digitSum.sort(function(a, b){return a - b;});
// Removing the duplicate elements
let hs1 = new Set(digitSum);
// "HashSet" is stores only unique elements
let vect2 = Array.from(hs1);
// Finding the sum and returning it
return findMMaxDistinctDigitSum(vect2, m);
}
// Driver Code
let n = 100, k = 80, m = 4;
// Function Call
document.write(findDistinctMnumbers(n, k, m));
// This code is contributed by rag2127
</script>
Producción:
24
Análisis de rendimiento:
- Complejidad del tiempo: en el enfoque dado, hay principalmente dos procesos que son los siguientes:
- Tiempo Complejidad para encontrar los factores de un número es: O(√(K))
- Complejidad de tiempo para ordenar y almacenar los elementos únicos: O(√(K)log(√(K)))
- Espacio auxiliar: en el enfoque dado, hay una array adicional que se usa para almacenar los factores del número K, que es: O(√(K))
Publicación traducida automáticamente
Artículo escrito por Aniket_Mallick y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA