Represent a number N in base -2

0 0 4 minutes read

Given an integer N, the task is to find base -2 representation of the number N in the form of a string, such that S₀* (- 2)⁰ + S₁* (- 2)¹ + … + S_k* (- 2)^k = N. The string should only consist of 0s and 1s and unless the string is equal to zero, the initial character should be 1.

Examples:

Input: N = -9
Output: 1011
Explanation: 1011 is -2 representation of -9
(-2)⁰+ (-2)¹+ (-2)³ = 1+ (-2) + (-8) = -9

Input: N = -7
Output: 1001

Approach: Follow the steps below to solve the problem:

Initialize an empty string S.
Iterate from N, until N is greater than zero.
- If N is even, append ‘0‘ in front of S and divide N by -2.
- Otherwise, append ‘1‘ in front of S, and decrement N by 1, and then divide N by -2.
If the string S is empty, then return ‘0‘
Finally, return the string S.

Below is the implementation of the above approach:

C++

// 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

// 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.

Python3

# 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#

// 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.

Javascript

<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>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!