Dado un número N y un dígito K (1 < K <= 9), la tarea es encontrar dos números enteros A y B tales que A + B = N y el dígito K no esté presente ni en A ni en B.
Ejemplos:
Entrada: N = 443, K = 4
Salida: 256, 187
Explicación:
Suma = 256 + 187 = 443 = N
Además, K(4) no está presente en 256 o 187
Por lo tanto, 256 y 187 son salidas válidas.Entrada: N = 678, K = 9
Salida: 311, 367
Explicación:
Suma = 311 + 367 = 678 = N
Además, K(9) no está presente en 311 o 367
Por lo tanto, 311 y 367 son salidas válidas.
Enfoque ingenuo:
un enfoque simple es ejecutar un ciclo y considerar cada elemento (digamos A) de 1 a N-1. Como la suma de A y B tiene que ser N, el B correspondiente será (N – A). Ahora verifique si tanto A como B contienen K o no, si no, imprima A y B. Este enfoque fallará para entradas más grandes como N = 10 18 .
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
el problema dado se puede resolver de manera mucho más eficiente. La idea es dividir cada dígito D de N en dos partes D1 y D2 de modo que D1 + D2 = D. Tome dos strings A y B , A contendrá todos los D1 y la string B contendrá todos los D2.
Por ejemplo, N = 4467 y K = 4
D D1 D2 4 2 2 4 2 2 6 6 0 7 7 0
Aquí, A será 2267 y B será 2200.
Los pasos detallados de este enfoque son los siguientes:
1. Atraviese N y considere cada uno de sus dígitos D.
2. Si el dígito D es igual a K, divídalo en D1 = D / 2 y D2 = D / 2 + D % 2.
D % 2 se suma a D2 para asegurar que D1 + D2 = D tanto para D par como impar 3. De lo contrario,
divídalo en D1 = D y D2 = 0.
4. Siga agregando D1 a la string A y D2 a la string B.
5. Finalmente, imprima las strings A y B, después de eliminar los ceros iniciales (si los hay).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <iostream>
using namespace std;
string removeLeadingZeros(string str)
{
// Count leading zeros
int i = 0;
int n = str.length();
while (str[i] == '0' && i < n)
i++;
// It removes i characters
// starting from index 0
str.erase(0, i);
return str;
}
void findPairs(int sum, int K)
{
string A, B;
A = "";
B = "";
string N = to_string(sum);
int n = N.length();
// Check each digit of the N
for (int i = 0; i < n; i++) {
int D = N[i] - '0';
// If digit is K break it
if (D == K) {
int D1, D2;
D1 = D / 2;
// For odd numbers
D2 = D / 2 + D % 2;
// Add D1 to A and D2 to B
A = A + char(D1 + '0');
B = B + char(D2 + '0');
}
// If the digit is not K,
// no need to break
// string D in A and 0 in B
else {
A = A + char(D + '0');
B = B + '0';
}
}
// Remove leading zeros
A = removeLeadingZeros(A);
B = removeLeadingZeros(B);
// Print the answer
cout << A << ", " << B << endl;
}
// Driver code
int main()
{
int N = 33673;
int K = 3;
findPairs(N, K);
return 0;
}
Java
// Java implementation of the above approach
class GFG{
static String removeLeadingZeros(String str)
{
// Count leading zeros
int i = 0;
int n = str.length();
while (str.charAt(i) == '0' && i < n)
i++;
// It removes i characters
// starting from index 0
str = str.substring(i);
return str;
}
static void findPairs(int sum, int K)
{
String A, B;
A = "";
B = "";
String N = String.valueOf(sum);
int n = N.length();
// Check each digit of the N
for(int i = 0; i < n; i++)
{
int D = N.charAt(i) - '0';
// If digit is K break it
if (D == K)
{
int D1, D2;
D1 = D / 2;
// For odd numbers
D2 = D / 2 + D % 2;
// Add D1 to A and D2 to B
A = A + (char)(D1 + '0');
B = B + (char)(D2 + '0');
}
// If the digit is not K,
// no need to break
// String D in A and 0 in B
else
{
A = A + (char)(D + '0');
B = B + '0';
}
}
// Remove leading zeros
A = removeLeadingZeros(A);
B = removeLeadingZeros(B);
// Print the answer
System.out.print(A + ", " + B + "\n");
}
// Driver code
public static void main(String[] args)
{
int N = 33673;
int K = 3;
findPairs(N, K);
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 implementation of the
# above approach
def removeLeadingZeros(Str):
# Count leading zeros
i = 0
n = len(Str)
while (Str[i] == '0' and i < n):
i += 1
# It removes i characters
# starting from index 0
Str = Str[i:]
return Str
def findPairs(Sum, K):
A = ""
B = ""
N = str(Sum)
n = len(N)
# Check each digit of the N
for i in range(n):
D = int(N[i]) - int('0')
# If digit is K break it
if (D == K):
D1 = D // 2;
# For odd numbers
D2 = (D // 2) + (D % 2)
# Add D1 to A and D2 to B
A = A + (str)(D1 + int('0'))
B = B + (str)(D2 + int('0'))
# If the digit is not K,
# no need to break
# String D in A and 0 in B
else:
A = A + (str)(D + int('0'))
B = B + '0'
# Remove leading zeros
A = removeLeadingZeros(A)
B = removeLeadingZeros(B)
# Print the answer
print(A + ", " + B)
# Driver code
N = 33673
K = 3
findPairs(N, K)
# This code is contributed divyeshrabadiya07
C#
// C# implementation of the above approach
using System;
class GFG{
static String removeLeadingZeros(String str)
{
// Count leading zeros
int i = 0;
int n = str.Length;
while (str[i] == '0' && i < n)
i++;
// It removes i characters
// starting from index 0
str = str.Substring(i);
return str;
}
static void findPairs(int sum, int K)
{
String A, B;
A = "";
B = "";
String N = String.Join("", sum);
int n = N.Length;
// Check each digit of the N
for(int i = 0; i < n; i++)
{
int D = N[i] - '0';
// If digit is K break it
if (D == K)
{
int D1, D2;
D1 = D / 2;
// For odd numbers
D2 = D / 2 + D % 2;
// Add D1 to A and D2 to B
A = A + (char)(D1 + '0');
B = B + (char)(D2 + '0');
}
// If the digit is not K,
// no need to break
// String D in A and 0 in B
else
{
A = A + (char)(D + '0');
B = B + '0';
}
}
// Remove leading zeros
A = removeLeadingZeros(A);
B = removeLeadingZeros(B);
// Print the answer
Console.Write(A + ", " + B + "\n");
}
// Driver code
public static void Main(String[] args)
{
int N = 33673;
int K = 3;
findPairs(N, K);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript implementation of
// the above approach
function removeLeadingZeros(str)
{
// Count leading zeros
var i = 0;
var n = str.length;
while (str[i] == '0' && i < n)
i++;
return str;
}
function findPairs(sum, K)
{
var A, B;
A = "";
B = "";
var N = (sum.toString());
var n = N.length;
// Check each digit of the N
for (var i = 0; i < n; i++) {
var D = N[i] - '0';
// If digit is K break it
if (D == K) {
var D1, D2;
D1 = parseInt(D / 2);
// For odd numbers
D2 = parseInt(D / 2) + D % 2;
// Add D1 to A and D2 to B
A = A +
String.fromCharCode(D1 + '0'.charCodeAt(0));
B = B +
String.fromCharCode(D2 + '0'.charCodeAt(0));
}
// If the digit is not K,
// no need to break
// string D in A and 0 in B
else {
A = A +
String.fromCharCode(D + '0'.charCodeAt(0));
B = B + '0';
}
}
// Remove leading zeros
A = removeLeadingZeros(A);
B = removeLeadingZeros(B);
// Print the answer
document.write( A + ", " + B );
}
// Driver code
var N = 33673;
var K = 3;
findPairs(N, K);
</script>
11671, 22002
Complejidad del tiempo: O(M)
Espacio auxiliar: O(M)
Aquí, M es el número de dígitos en N.
Publicación traducida automáticamente
Artículo escrito por sri_srajit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA