Se nos da un número n y una base negativa negBase , necesitamos representar n en esa base negativa. La base negativa funciona de manera similar a la base positiva. Por ejemplo, en base 2, multiplicamos los bits por 1, 2, 4, 8 y así sucesivamente para obtener el número real en decimal. En el caso de la base -2, necesitamos multiplicar los bits con 1, -2, 4, -8 y así sucesivamente para obtener el número en decimal.
Ejemplos:
Input : n = 13, negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Es posible representar un número en cualquier base negativa con el mismo procedimiento (consulte Wiki para obtener más detalles). Para simplificar (para deshacerse de los caracteres A, B, etc. en la salida), estamos permitiendo que nuestra base esté entre -2 y -10 solamente.
Podemos resolver este problema de manera similar a resolver un problema con bases positivas, pero una cosa importante para recordar es que el resto siempre será positivo ya sea que trabajemos con base positiva o base negativa, pero en la mayoría de los compiladores, el resultado de dividir un número negativo entre un número negativo. se redondea hacia 0, por lo general deja un resto negativo.
Entonces, cada vez que obtenemos un resto negativo, podemos convertirlo en positivo como se muestra a continuación,
Let
n = (?negBase) * quotient + remainder
= (?negBase) * quotient + negBase ? negBase + negBase
= (?negBase) * (quotient + 1) + (remainder + negBase).
So if after doing "remainder = n % negBase" and
"n = n/negBase", we get negative remainder, we do
following.
remainder = remainder + (-negBase)
n = n + 1
Example : n = -4, negBase = -3
In C++, we get
remainder = n % negBase = -4/-3 = -1
n = n/negBase [Next step for base conversion]
= -4/-3
= 1
To avoid negative remainder, we do,
remainder = -1 + (-negBase) = -1 - (-3) = 2
n = n + 1 = 1 + 1 = 2.
Entonces, cuando obtengamos un resto negativo, lo haremos positivo al agregarle el valor absoluto de la base y agregar 1 a nuestro cociente.
El enfoque explicado anteriormente se implementa en el siguiente código,
C++
// C/C++ program to convert n into negative base form
#include <bits/stdc++.h>
using namespace std;
// Utility method to convert integer into string
string toString(int n)
{
string str;
stringstream ss;
ss << n;
ss >> str;
return str;
}
// Method to convert n to base negBase
string toNegativeBase(int n, int negBase)
{
// If n is zero then in any base it will be 0 only
if (n == 0)
return "0";
string converted = "";
while (n != 0)
{
// Get remainder by negative base, it can be
// negative also
int remainder = n % negBase;
n /= negBase;
// if remainder is negative, add abs(base) to
// it and add 1 to n
if (remainder < 0)
{
remainder += (-negBase);
n += 1;
}
// convert remainder to string add into the result
converted = toString(remainder) + converted;
}
return converted;
}
// Driver code to test above methods
int main()
{
int n = 13;
int negBase = -2;
cout << toNegativeBase(n, negBase);
return 0;
}
Java
// Java program to convert n into
// negative base form
class GFG
{
// Method to convert n to base negBase
static String toNegativeBase(int n, int negBase)
{
// If n is zero then in any base
// it will be 0 only
if (n == 0)
return "0";
String converted = "";
while (n != 0)
{
// Get remainder by negative base,
// it can be negative also
int remainder = n % negBase;
n /= negBase;
// if remainder is negative,
// add Math.abs(base) to it
// and add 1 to n
if (remainder < 0)
{
remainder += (-negBase);
n += 1;
}
// convert remainder to String add into the result
converted = String.valueOf(remainder) + converted;
}
return converted;
}
// Driver Code
public static void main(String[] args)
{
int n = 13;
int negBase = -2;
System.out.print(toNegativeBase(n, negBase));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to convert n into # negative base form # Method to convert n to base negBase def toNegativeBase(n, negBase): # If n is zero then in any base it # will be 0 only if (n == 0): return "0" converted = "01" while (n != 0): # Get remainder by negative base, # it can be negative also remainder = n % (negBase) n = int(n/negBase) # if remainder is negative, add # abs(base) to it and add 1 to n if (remainder < 0): remainder += ((-1) * negBase) n += 1 # convert remainder to string add # into the result converted = str(remainder) + converted return converted # Driver Code if __name__ == '__main__': n = 13 negBase = -2 print(toNegativeBase(n, negBase)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to convert n into
// negative base form
using System;
class GFG
{
// Method to convert n to base negBase
static String toNegativeBase(int n, int negBase)
{
// If n is zero then in any base
// it will be 0 only
if (n == 0)
return "0";
String converted = "";
while (n != 0)
{
// Get remainder by negative base,
// it can be negative also
int remainder = n % negBase;
n /= negBase;
// if remainder is negative,
// add Math.Abs(base) to it
// and add 1 to n
if (remainder < 0)
{
remainder += (-negBase);
n += 1;
}
// convert remainder to String add into the result
converted = String.Join("", remainder) + converted;
}
return converted;
}
// Driver Code
public static void Main(String[] args)
{
int n = 13;
int negBase = -2;
Console.Write(toNegativeBase(n, negBase));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to convert n into
// negative base form
// Method to convert n to base negBase
function toNegativeBase(n, negBase)
{
// If n is zero then in any base
// it will be 0 only
if (n == 0)
return "0";
let converted = "01";
while (n != 0)
{
// Get remainder by negative base,
// it can be negative also
let remainder = (-1)*(Math.abs(n) % Math.abs(negBase));
n = parseInt(n/negBase);
// if remainder is negative,
// add Math.abs(base) to it
// and add 1 to n
if (remainder < 0)
{
remainder += ((-1)*negBase);
n += 1;
}
// convert remainder to String add into the result
converted = remainder.toString() + converted;
}
return converted;
}
// Driver Code
let n = 13;
let negBase = -2;
document.write(toNegativeBase(n, negBase),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
11101
Complejidad de tiempo: O(N)
Espacio auxiliar: O(1)
Referencia:
https://en.wikipedia.org/wiki/Negative_base
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA