Convert integer to NAF form

Question

Convert a given integer into its Non-Adjacent Form (NAF) representation such that no two non-zero digits are adjacent, and prove that the resulting form has minimal Hamming weight. Explain the algorithm and analyze its complexity.

Convert Integer to Non-Adjacent Form

Given an integer n, convert it to its Non-Adjacent Form (NAF): a signed-binary representation with digits in {-1, 0, 1} such that no two non-zero digits are adjacent. Return the digits as a list in least-significant-first order. If n = 0, return [0].

Constraints

• -10^18 <= n <= 10^18
• Output digits must be in {-1, 0, 1}
• No two non-zero digits are adjacent in the output
• Return digits in least-significant-first order
• For n = 0, return [0]

Examples

Example 1

Input: n = 15
Output: [-1, 0, 0, 0, 1]

Explanation: 15 = (-1)2^0 + 02^1 + 02^2 + 02^3 + 1*2^4. Non-zero digits are at positions 0 and 4 only.

Example 2

Input: n = -5
Output: [-1, 0, -1]

Explanation: -5 = (-1)2^0 + 02^1 + (-1)*2^2. Non-zero digits are at positions 0 and 2 only.

Hints

1. Process n from least significant bit upward. If n is even, the current digit is 0.
2. If n is odd, set the current digit to 2 - (n mod 4), which yields 1 when n mod 4 == 1 and -1 when n mod 4 == 3.
3. After choosing the digit a in {-1, 1} for an odd n, divide (n - a) by 2; this ensures the next step is even, preventing adjacent non-zero digits.
4. Handle n = 0 as a special case by returning [0].

Approach

The algorithm builds the NAF from least significant position upward. For an odd n, choose a in {1, -1} so that n - a is divisible by 2: set a = 2 - (n mod 4), which yields 1 when the remainder is 1 and -1 when it is 3 (Python's modulo is always non-negative). Then update n := (n - a) / 2. For even n, set the digit to 0 and update n := n / 2. This guarantees that after placing a non-zero digit, the next step is even, so no two non-zero digits are adjacent. The produced representation is the unique NAF and has minimal Hamming weight among all signed-binary expansions with digits in {-1,0,1}. Intuition: any adjacent non-zero pair could be reduced by carrying (e.g., 1,1 at positions i and i+1 can be replaced by -1 at i and +1 at i+2), strictly decreasing the number of non-zero digits; the greedy choice eliminates such adjacencies by construction, yielding minimal weight.

• Time complexity: O(log |n|)
• Space complexity: O(log |n|)