Quick Overview

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.

Convert integer to NAF form

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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

Overview: 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

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

Loading coding console...

Show the approach

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|)