Convert integer to NAF form
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### 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.
Quick Answer: This question evaluates understanding of number representations (Non-Adjacent Form), bit-level optimization, and formal proof techniques for demonstrating minimal Hamming weight, together with algorithmic complexity analysis.
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]
Solution
from typing import List
def naf(n: int) -> List[int]:
if n == 0:
return [0]
digits: List[int] = []
while n != 0:
if n % 2 != 0:
a = 2 - (n % 4) # 1 if n % 4 == 1, -1 if n % 4 == 3
digits.append(a)
n = (n - a) // 2
else:
digits.append(0)
n //= 2
return digits
Explanation
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|).
Hints
- Process n from least significant bit upward. If n is even, the current digit is 0.
- 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.
- 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.
- Handle n = 0 as a special case by returning [0].