Convert Integer to Non-Adjacent Form

Implement toNAF(n) that converts an integer n (allow negative n) to its Non-Adjacent Form using digits from {-1, 0, 1} with no two adjacent nonzero digits, returning digits least-significant-first. Implement fromNAF(digits) to convert a NAF sequence back to the integer. Prove correctness, show why NAF minimizes the number of nonzero digits among signed-binary representations, analyze time and space complexity, and handle edge cases (n = 0, very large magnitude). As an extension, show how to compute n * k efficiently using the NAF of k to reduce additions.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Convert Integer to Non-Adjacent Form (toNAF)

The Non-Adjacent Form (NAF) of an integer is a signed-binary representation using digits from {-1, 0, 1} in which no two consecutive digits are both nonzero. Every integer has a unique NAF, and among all signed-binary representations of a value it has the minimum possible number of nonzero digits (on average about n/3 nonzeros for an n-bit number, vs. n/2 for ordinary binary). This makes it the standard tool for speeding up multiplication and modular exponentiation, since each nonzero digit costs one add/subtract.

Implement toNAF(n) that converts an integer n (which may be negative) to its NAF, returning the digits least-significant-first as a list of values from {-1, 0, 1}.

Key idea: repeatedly look at the value. If it is even, emit a 0 and halve it. If it is odd, choose the digit z in {-1, 1} so that n - z is divisible by 4 (this forces the NEXT digit to be 0, guaranteeing the non-adjacency property). The choice is z = 2 - (n mod 4): that yields +1 when n ≡ 1 (mod 4) and -1 when n ≡ 3 (mod 4). Emit z, subtract it from n, then halve. Stop when n reaches 0. By convention NAF(0) is [0].

Proof sketch of correctness: when n is odd, n mod 4 is 1 or 3. If n ≡ 1 (mod 4) we pick z=1, making n-1 ≡ 0 (mod 4), so (n-1)/2 is even and the next emitted digit is 0. If n ≡ 3 (mod 4) we pick z=-1, making n+1 ≡ 0 (mod 4), again forcing the next digit to 0. Thus no two adjacent nonzero digits ever appear, and the running value provably converges to 0 (its magnitude strictly decreases each two steps), so the loop terminates and reconstructs n exactly.

Minimality: NAF is the unique signed-binary representation with no two adjacent nonzeros, and a classic result (Reitwiesner) shows this canonical form minimizes the Hamming weight (count of nonzero digits) over all signed-binary representations of the same integer — which is exactly why it minimizes additions in scalar multiplication.

Constraints

• n may be any integer, positive, negative, or zero.
• Digits returned are exactly from the set {-1, 0, 1}.
• No two adjacent returned digits are both nonzero.
• Output is least-significant-digit first.
• By convention toNAF(0) returns [0].

Examples

Example 1

Input: (0,)
Output: [0]

Explanation: Zero is the base case; NAF(0) is defined as [0].

Example 2

Input: (1,)
Output: [1]

Explanation: 1 is odd, 1 mod 4 = 1 so z=+1; after subtracting, value is 0. Single digit 1.

Hints

1. Process the number bit by bit from the least-significant end, like ordinary binary conversion but allowing the digit -1.
2. When the current value is odd, you must emit -1 or +1. Pick whichever makes the value divisible by 4 after subtracting it — that forces the very next digit to be 0.
3. The clean formula for the odd case is z = 2 - (n mod 4): it gives +1 when n ≡ 1 (mod 4) and -1 when n ≡ 3 (mod 4). Subtract z, then integer-divide by 2.
4. Floor division (Python //, which rounds toward -infinity) makes the negative case work without special handling.

Convert Non-Adjacent Form Back to Integer (fromNAF)

Given a Non-Adjacent Form (NAF) sequence — a list of signed-binary digits from {-1, 0, 1}, least-significant-first — reconstruct the integer it represents.

The value of a digit list d is simply the weighted sum sum(d[i] * 2^i). The digits being from {-1, 0, 1} (rather than {0, 1}) is exactly what lets the representation be signed; the reconstruction does not actually depend on the non-adjacency property, so this same routine inverts any signed-binary digit list.

Implement fromNAF(digits) returning the integer. The numerically stable way to evaluate it is Horner's method from the most-significant digit down: start with value 0 and repeatedly do value = value * 2 + digit, walking the list from its last element to its first. An empty list represents 0.

This is the inverse of toNAF, so fromNAF(toNAF(n)) == n for every integer n. As the extension in the prompt notes, this pairing is what powers fast multiplication n*k: precompute toNAF(k), then accumulate shifted copies of n with a +n for each +1 digit and a -n for each -1 digit, performing about |k|'s NAF-weight additions/subtractions instead of one per binary one.

Constraints

• Each digit is from {-1, 0, 1}.
• Input is least-significant-digit first (matching toNAF's output order).
• An empty list represents the integer 0.
• Must be the exact inverse of toNAF: fromNAF(toNAF(n)) == n for all n.

Examples

Example 1

Input: ([0],)
Output: 0

Explanation: A single zero digit decodes to 0, matching toNAF(0).

Example 2

Input: ([1],)
Output: 1

Explanation: One digit of value 1 at position 0 gives 1·2^0 = 1.

Hints

1. The value is just sum(digits[i] * 2**i); the non-adjacency property is not needed to decode.
2. Use Horner's rule from the most-significant digit (the last element) down: value = value*2 + digit. This avoids computing powers of two explicitly.
3. Walking the list in reverse keeps the accumulator exact even when some digits are -1.
4. Handle the empty list as 0 — the loop body simply never runs.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Implement toNAF(n) that converts an integer n (allow negative n) to its Non-Adjacent Form using digits from {-1, 0, 1} with no two adjacent nonzero digits, returning digits least-significant-first. Implement fromNAF(digits) to convert a NAF sequence back to the integer. Prove correctness, show why NAF minimizes the number of nonzero digits among signed-binary representations, analyze time and space complexity, and handle edge cases (n = 0, very large magnitude). As an extension, show how to compute n * k efficiently using the NAF of k to reduce additions.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.