Dados dos números, N y M , la tarea es encontrar dos números formados por M como todos sus dígitos, de modo que su diferencia sea divisible por N.
Ejemplos:
Entrada: N = 8, M = 2
Salida: 22 222
Explicación: La diferencia entre 222 y 22 (200) es divisible por 8
Entrada: N = 17, M = 6
Salida: 6 66666666666666666
Enfoque:
En este problema, tenemos que encontrar números que constan de un solo dígito único. Digamos que M es igual a 2, luego tenemos que encontrar A y B a partir de números como 2, 22, 222, 2222… y así sucesivamente. La diferencia entre A y B debe ser divisible por N. Para que esta condición se cumpla, tenemos que elegir A y B de manera que el resto de A y B cuando se divide por N , sea el mismo.
Para un dígito de longitud N+1 , que consta de un solo dígito único M , tendremos N+1 números. Si dividimos estos N+1 números por N tendremos N+1 residuos que irán desde [0, N]. Dado que los números pueden exceder el rango de valores enteros, estamos almacenando la longitud restante del número como pares clave-valor en un mapa. Una vez que se produce un resto con un valor ya emparejado en el mapa, la longitud actual y las longitudes asignadas son las longitudes de los números deseados.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ implementation
// of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to implement
// the above approach
void findNumbers(int N, int M)
{
int m = M;
// Hashmap to store
// remainder-length of the
// number as key-value pairs
map<int, int> remLen;
int len, remainder;
// Iterate till N + 1 length
for (len = 1; len <= N + 1; ++len) {
remainder = M % N;
// Search remainder in the map
if (remLen.find(remainder)
== remLen.end())
// If remainder is not
// already present insert
// the length for the
// corresponding remainder
remLen[remainder] = len;
else
break;
// Keep increasing M
M = M * 10 + m;
// To keep M in range of integer
M = M % N;
}
// Length of one number
// is the current Length
int LenA = len;
// Length of the other number
// is the length paired with
// current remainder in map
int LenB = remLen[remainder];
for (int i = 0; i < LenB; ++i)
cout << m;
cout << " ";
for (int i = 0; i < LenA; ++i)
cout << m;
return;
}
// Driver code
int main()
{
int N = 8, M = 2;
findNumbers(N, M);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// Function to implement
// the above approach
static void findNumbers(int N, int M)
{
int m = M;
// Hashmap to store
// remainder-length of the
// number as key-value pairs
Map<Integer, Integer> remLen = new HashMap<>();
int len, remainder = 0;
// Iterate till N + 1 length
for(len = 1; len <= N + 1; ++len)
{
remainder = M % N;
// Search remainder in the map
if (!remLen.containsKey(remainder))
{
// If remainder is not
// already present insert
// the length for the
// corresponding remainder
remLen.put(remainder, len);
}
else
{
break;
}
// Keep increasing M
M = M * 10 + m;
// To keep M in range of integer
M = M % N;
}
// Length of one number
// is the current Length
int LenA = len;
// Length of the other number
// is the length paired with
// current remainder in map
int LenB = remLen.getOrDefault(remainder, 0);
for(int i = 0; i < LenB; ++i)
System.out.print(m);
System.out.print(" ");
for(int i = 0; i < LenA; ++i)
System.out.print(m);
}
// Driver code
public static void main(String[] args)
{
int N = 8, M = 2;
findNumbers(N, M);
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation
# of the above approach
# Function to implement
# the above approach
def findNumbers(N, M):
m = M
# Hashmap to store
# remainder-length of the
# number as key-value pairs
remLen = {}
# Iterate till N + 1 length
for len1 in range(1, N + 1, 1):
remainder = M % N
# Search remainder in the map
if (remLen.get(remainder) == None):
# If remainder is not
# already present insert
# the length for the
# corresponding remainder
remLen[remainder] = len1
else:
break
# Keep increasing M
M = M * 10 + m
# To keep M in range of integer
M = M % N
# Length of one number
# is the current Length
LenA = len1
# Length of the other number
# is the length paired with
# current remainder in map
LenB = remLen[remainder]
for i in range(LenB):
print(m, end = "")
print(" ", end = "")
for i in range(LenA):
print(m, end = "")
return
# Driver code
if __name__ == '__main__':
N = 8
M = 2
findNumbers(N, M)
# This code is contributed by Bhupendra_Singh
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to implement
// the above approach
static void findNumbers(int N, int M)
{
int m = M;
// To store remainder-length of
// the number as key-value pairs
Dictionary<int,
int> remLen = new Dictionary<int,
int>();
int len, remainder = 0;
// Iterate till N + 1 length
for(len = 1; len <= N + 1; ++len)
{
remainder = M % N;
// Search remainder in the map
if (!remLen.ContainsKey(remainder))
{
// If remainder is not
// already present insert
// the length for the
// corresponding remainder
remLen.Add(remainder, len);
}
else
{
break;
}
// Keep increasing M
M = M * 10 + m;
// To keep M in range of integer
M = M % N;
}
// Length of one number
// is the current Length
int LenA = len;
// Length of the other number
// is the length paired with
// current remainder in map
int LenB = remLen[remainder];
for(int i = 0; i < LenB; ++i)
Console.Write(m);
Console.Write(" ");
for(int i = 0; i < LenA; ++i)
Console.Write(m);
}
// Driver code
public static void Main(String[] args)
{
int N = 8, M = 2;
findNumbers(N, M);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation of the above approach
// Function to implement
// the above approach
function findNumbers(N, M)
{
let m = M;
// To store remainder-length of
// the number as key-value pairs
let remLen = new Map();
let len, remainder = 0;
// Iterate till N + 1 length
for(len = 1; len <= N + 1; ++len)
{
remainder = M % N;
// Search remainder in the map
if (!remLen.has(remainder))
{
// If remainder is not
// already present insert
// the length for the
// corresponding remainder
remLen.set(remainder, len);
}
else
{
break;
}
// Keep increasing M
M = M * 10 + m;
// To keep M in range of integer
M = M % N;
}
// Length of one number
// is the current Length
let LenA = len;
// Length of the other number
// is the length paired with
// current remainder in map
let LenB = remLen.get(remainder);
for(let i = 0; i < LenB; ++i)
document.write(m);
document.write(" ");
for(let i = 0; i < LenA; ++i)
document.write(m);
}
let N = 8, M = 2;
findNumbers(N, M);
// This code is contributed by divyeshrabadiya07.
</script>
22 222
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shivamsinghal1012 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA