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