число п і негативна основа negBase нам потрібно представити n у цій від’ємній основі. Негативна база працює подібно до позитивної. Наприклад, у основі 2 ми множимо біти на 1 2 4 8 і так далі, щоб отримати фактичне число в десятковому вигляді. У разі основи -2 нам потрібно помножити біти на 1 -2 4 -8 і так далі, щоб отримати число в десятковому вигляді.
приклади:
скільки міст у Сполучених Штатах Америки
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Число можна представити будь-якою від’ємною основою за допомогою тієї ж процедури (див тиждень для деталей). Для простоти (щоб позбутися символів A B тощо у виводі) ми дозволяємо нашій базі бути лише між -2 і -10.
Ми можемо розв’язати цю задачу подібно до розв’язання задачі з додатними основами, але пам’ятайте одну важливу річ: залишок завжди буде додатним, незалежно від того, працюємо ми з додатною чи від’ємною основою, але в більшості компіляторів результат ділення від’ємного числа на від’ємне число округлюється до 0, залишаючи зазвичай від’ємний залишок.
Отже, коли ми отримуємо від’ємний залишок, ми можемо перетворити його на додатний, як показано нижче
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.
Отже, коли ми отримаємо від’ємний залишок, ми зробимо його додатним, додавши до нього абсолютне значення основи та додавши 1 до нашої частки.
Описаний вище підхід реалізовано в коді нижче
збереження gimp як jpegC++
// C/C++ program to convert n into negative base form #include
// 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
# 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# 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
<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)''); // This code is contributed by shinjanpatra </script>
Вихід:
11101
Часова складність: O(N)
Допоміжний простір: О(1)
Посилання:
https://en.wikipedia.org/wiki/Negative_base