Given an integer N, the task is to find base -2 representation of the number N in the form of a string, such that S0 * (- 2)0 + S1 * (- 2)1 + … + Sk * (- 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)0+ (-2)1+ (-2)3 = 1+ (-2) + (-8) = -9Input: 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 -2string 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 Codeint main(){ // Given Input int N = -9; // Function Call cout << BaseConversion(N); return 0;} |
Java
// Java Program for above approachclass 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 -2def 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 InputN = -9# Function Callprint(BaseConversion(N))# This code is contributed by _saurabh_jaiswal |
C#
// C# Program for above approachusing System;using System.Collections.Generic;class GFG{// Function to convert N to// equivalent representation in base -2static 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 Codepublic 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:
1011
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
