Dado un número N, encuentre la mínima suma posible de dígitos que se puede obtener de un múltiplo positivo de N.
Restricciones : 1<=N<=10^5.
Ejemplos:
Input : N = 6 Output : 3 Explanation: 6*2 = 12, sum of digits is 1+2 = 3. Input : N = 20 Output : 1 20*5 = 100, sum of digits is 1+0+0=1
Enfoque : El problema se basa totalmente en la observación. Para N = 6, la respuesta es 12.
Entonces podemos escribir 12 como: 1-(*10)–>10–(+1)–>11–(+1)–>12. Lo que describe la secuencia es que podemos escribir cualquier número >=1, como la suma de +1 y el producto de *10, comenzando con 1.
Otra observación es que, cuando sumamos +1 al dígito, la suma de los dígitos aumenta en +1, a menos que el último dígito sea 9.
La segunda observación es que, cuando multiplicamos el dígito por 10, la suma de los dígitos permanece constante.
Ahora, como queremos un múltiplo de N, cualquier múltiplo de N % N será 0.
Entonces, tomando el análisis anterior, podemos construir un gráfico de K vértices, para cualquier vértice X, el peso del Node de X a X+1 será uno, y el peso del Node de X a (X*10)%N será sea 0. Tomamos el módulo N ya que el vértice se encuentra entre 0 y N-1.
La respuesta será la distancia más corta de 1 a 0, debido a (Cualquier múltiplo de N) mod N = 0.
Podemos usar el teorema de Dijkstra para encontrar la distancia más corta entre 1 y 0. Sea d. La respuesta será 1+d, ya que también debemos considerar el borde 0 a 1.
La complejidad temporal de esta solución será O(E+VLogV) = O(N+NLogN) = O(NlogN) ya que viajaremos como máximo N vértices y aristas.
Una cosa más a tener en cuenta es que, después de xyz..9, el siguiente dígito será abc..0, pero no afectará nuestra respuesta.
Prueba : tomemos el ejemplo de N = 11, la respuesta es 2. Es de 11*1 = 11 y 11*10 = 110.
Dado que 110 es un múltiplo de 10 de N y también una respuesta, ya hemos llegado a la respuesta porque si 110 es un múltiplo de 10 de N, entonces debe existir un número menor que este sin ceros a la izquierda en nuestra respuesta, es decir, 11.
Entonces, o superaremos el múltiplo de 10 de N, si no es una respuesta, o lo haremos ya he llegado a la respuesta antes si la respuesta es un múltiplo de 10 de N.
A continuación se muestra la implementación del enfoque anterior:
#include <bits/stdc++.h>
using namespace std;
const int Maxx = 100005;
int N;
vector<pair<int, int> > Graph[Maxx];
/// Dijkartas algorithm to find the shortest distance
void Dijkartas(int source)
{
priority_queue<pair<int, int>, vector<pair<int, int> >,
greater<pair<int, int> > > PQ;
// Initialize all distances to be infinity
vector<int> Distance(N + 2, 1e9);
// Push source in Priority Queue
PQ.push(make_pair(0, source));
int src = source;
Distance[src] = 0;
while (!PQ.empty()) {
int current = PQ.top().second;
PQ.pop();
for (auto& neighbours : Graph[current]) {
int v = neighbours.first;
int weight = neighbours.second;
if (Distance[v] > Distance[current] + weight) {
Distance[v] = Distance[current] + weight;
PQ.push(make_pair(Distance[v], v));
}
}
}
cout << "Minimum possible sum of digits is " <<
1 + Distance[0] << endl;
return;
}
// Function to calculate the minimum possible sum of digits
void minSumDigits(int N)
{
// Build a graph of N vertices with edge weight 1
for (int i = 1; i <= N; ++i) {
int From = (i) % N;
int To = (i + 1) % N;
int Wt = 1;
Graph[From].push_back(make_pair(To, Wt));
}
// In the same graph add weights 0 to 10's multiple of node X
for (int i = 1; i <= N; ++i) {
int From = (i) % N;
int To = (10 * i) % N;
int Wt = 0;
Graph[From].push_back(make_pair(To, Wt));
}
// Run dijartas to find the shortest distance from 1 to 0
Dijkartas(1);
return;
}
// Driver Code
int main()
{
N = 19;
minSumDigits(N);
return 0;
}
Minimum possible sum of digits is 2