1441. Minus-Two Notation
An old tally device displays numbers with only two symbols, 0 and 1, but the place values are the powers of -2: 1, -2, 4, -8, 16, and so on. Because the signs alternate, every integer, positive or negative, can be shown without a minus sign in front.
Given an integer n, return the string of 0 and 1 digits, most significant digit first, whose value in base -2 equals n. The representation has no leading zeros, and zero itself is written as "0". For example 6 is "11010" because 16 - 8 + 0 - 2 + 0 = 6. The representation is unique, so there are no tie-breaks. Intended time is O(log |n|) with O(1) extra space beyond the output.
Example 1
- Input:
- n = 6
- Output:
- "11010"
- Explanation:
16 - 8 + 0 - 2 + 0 = 6, so the digits are 11010.
Example 2
- Input:
- n = -3
- Output:
- "1101"
- Explanation:
-3 = -8 + 4 + 0 + 1, so the digits are 1101.
Example 3
- Input:
- n = 0
- Output:
- "0"
- Explanation:
Zero is written as the single digit 0.
Constraints
-1015 ≤ n ≤ 1015
Use 64-bit integers; a remainder may come out negative in some languages and must be normalised to 0 or 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log |n|)
- Space
- O(log |n|)