Representar un número N en base -2

Dado un número entero N, la tarea es encontrar la representación en base -2 del número N en forma de string , tal que S ₀ * (- 2) ⁰ + S ₁ * (- 2) ¹ + … + S _k * (- 2) ^k = norte . La string solo debe constar de 0 y 1 y, a menos que la string sea igual a cero, el carácter inicial debe ser 1 .

Ejemplos:

Entrada: N = -9
Salida: 1011
Explicación: 1011 es la representación -2 de -9
(-2) ⁰ + (-2) ¹ + (-2) ³ = 1+ (-2) + (-8) = – 9

Entrada: N = -7
Salida: 1001

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice una string vacía S .
• Iterar desde N, hasta que N sea mayor que cero.
  • Si N es par, agregue ‘ 0 ‘ delante de S y divida N por -2 .
  • De lo contrario, agregue ‘ 1 ‘ delante de S , disminuya N en 1 y luego divida N entre -2 .
• Si la string S está vacía, devuelve ‘ 0 ‘
• Finalmente, devuelva la string S.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to convert N to
// equivalent representation in base -2
string BaseConversion(int N)
{
 
    // Stores the required answer
    string s = "";
 
    // Iterate until N is
    // not equal to zero
    while (N != 0) {
 
        // If N is Even
        if (N % 2 == 0) {
 
            // Add char '0' in
            // front of string
            s = "0" + s;
        }
        else {
 
            // Add char '1' in
            // front of string
            s = "1" + s;
 
            // Decrement N by 1
            N--;
        }
 
        // Divide N by -2
        N /= -2;
    }
 
    // If string is empty,
    // that means N is zero
    if (s == "") {
 
        // Put '0' in string s
        s = "0";
    }
    return s;
}
 
// Driver Code
int main()
{
 
    // Given Input
    int N = -9;
 
    // Function Call
    cout << BaseConversion(N);
    return 0;
}

// Java Program for above approach
class GFG {
    // Function to convert N to
    // equivalent representation in base -2
    public static String BaseConversion(int N) {
 
        // Stores the required answer
        String s = "";
 
        // Iterate until N is
        // not equal to zero
        while (N != 0) {
 
            // If N is Even
            if (N % 2 == 0) {
 
                // Add char '0' in
                // front of string
                s = "0" + s;
            } else {
 
                // Add char '1' in
                // front of string
                s = "1" + s;
 
                // Decrement N by 1
                N--;
            }
 
            // Divide N by -2
            N /= -2;
        }
 
        // If string is empty,
        // that means N is zero
        if (s == "") {
 
            // Put '0' in string s
            s = "0";
        }
        return s;
    }
 
    // Driver Code
    public static void main(String args[]) {
 
        // Given Input
        int N = -9;
 
        // Function Call
        System.out.println(BaseConversion(N));
    }
 
}
 
// This code is contributed by _saurabh_jaiswal.

# Python Program for the above approach
 
# Function to convert N to
# equivalent representation in base -2
def BaseConversion(N):
 
    # Stores the required answer
    s = ""
 
    # Iterate until N is
    # not equal to zero
    while (N != 0):
 
        # If N is Even
        if (N % 2 == 0):
 
            # Add char '0' in
            # front of string
            s = "0" + s
 
        else:
 
            # Add char '1' in
            # front of string
            s = "1" + s
 
            # Decrement N by 1
            N -= 1
 
        # Divide N by -2
        N /= -2
 
    # If string is empty,
    # that means N is zero
    if (s == ""):
 
        # Put '0' in string s
        s = "0"
 
    return s
 
 
# Driver Code
 
# Given Input
N = -9
 
# Function Call
print(BaseConversion(N))
 
# This code is contributed by _saurabh_jaiswal

// C# Program for above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to convert N to
// equivalent representation in base -2
static string BaseConversion(int N)
{
 
    // Stores the required answer
    string s = "";
 
    // Iterate until N is
    // not equal to zero
    while (N != 0) {
 
        // If N is Even
        if (N % 2 == 0) {
 
            // Add char '0' in
            // front of string
            s = "0" + s;
        }
        else {
 
            // Add char '1' in
            // front of string
            s = "1" + s;
 
            // Decrement N by 1
            N--;
        }
 
        // Divide N by -2
        N /= -2;
    }
 
    // If string is empty,
    // that means N is zero
    if (s == "") {
 
        // Put '0' in string s
        s = "0";
    }
    return s;
}
 
// Driver Code
public static void Main()
{
 
    // Given Input
    int N = -9;
 
    // Function Call
    Console.Write(BaseConversion(N));
}
}
 
// This code is contributed by bgangwar59.

<script>
       // JavaScript Program for the above approach
 
       // Function to convert N to
       // equivalent representation in base -2
       function BaseConversion(N)
       {
 
           // Stores the required answer
           let s = "";
 
           // Iterate until N is
           // not equal to zero
           while (N != 0) {
 
               // If N is Even
               if (N % 2 == 0) {
 
                   // Add char '0' in
                   // front of string
                   s = "0" + s;
               }
               else {
 
                   // Add char '1' in
                   // front of string
                   s = "1" + s;
 
                   // Decrement N by 1
                   N--;
               }
 
               // Divide N by -2
               N /= -2;
           }
 
           // If string is empty,
           // that means N is zero
           if (s == "") {
 
               // Put '0' in string s
               s = "0";
           }
           return s;
       }
 
       // Driver Code
 
 
       // Given Input
       let N = -9;
 
       // Function Call
       document.write(BaseConversion(N));
 
   // This code is contributed by Potta Lokesh
   </script>

1011

Complejidad temporal: O(N)
Espacio auxiliar: O(1)