PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

Convert Integer to Non-Adjacent Form evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

  • Medium
  • Salesforce
  • Coding & Algorithms
  • Software Engineer

Convert Integer to Non-Adjacent Form

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

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.

Quick Answer: Convert Integer to Non-Adjacent Form evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

Input: (0,)

Expected Output: [0]

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

Input: (1,)

Expected Output: [1]

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

Input: (7,)

Expected Output: [-1, 0, 0, 1]

Explanation: 7 = 8 - 1 = 2^3 - 2^0, so the NAF is (-1)·1 + 0·2 + 0·4 + 1·8 = 7 with only two nonzero digits instead of three ones in 0b111.

Input: (3,)

Expected Output: [-1, 0, 1]

Explanation: 3 = 4 - 1: digits give -1 + 0·2 + 1·4 = 3, replacing binary 11 (weight 2) with the same weight but non-adjacent form.

Input: (-7,)

Expected Output: [1, 0, 0, -1]

Explanation: -7 = -8 + 1 = 1·1 + 0·2 + 0·4 + (-1)·8. Negative inputs are handled directly by floor division.

Input: (2,)

Expected Output: [0, 1]

Explanation: 2 is even: emit 0, halve to 1, which emits 1. Result 0·1 + 1·2 = 2.

Input: (15,)

Expected Output: [-1, 0, 0, 0, 1]

Explanation: 15 = 16 - 1 = 2^4 - 2^0: four binary ones collapse to two nonzero NAF digits.

Input: (1073741823,)

Expected Output: [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

Explanation: 2^30 - 1 (thirty binary ones) compresses to exactly two nonzero NAF digits: -2^0 + 2^30, demonstrating the large-magnitude minimal-weight property.

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

Input: ([0],)

Expected Output: 0

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

Input: ([1],)

Expected Output: 1

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

Input: ([-1, 0, 0, 1],)

Expected Output: 7

Explanation: (-1)·1 + 0·2 + 0·4 + 1·8 = -1 + 8 = 7, the inverse of toNAF(7).

Input: ([-1, 0, 1],)

Expected Output: 3

Explanation: (-1)·1 + 0·2 + 1·4 = -1 + 4 = 3.

Input: ([1, 0, 0, -1],)

Expected Output: -7

Explanation: 1·1 + 0·2 + 0·4 + (-1)·8 = 1 - 8 = -7, showing negative reconstruction.

Input: ([0, 1],)

Expected Output: 2

Explanation: 0·1 + 1·2 = 2.

Input: ([],)

Expected Output: 0

Explanation: Empty digit list is the convention for 0; the loop never executes.

Input: ([-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],)

Expected Output: 1073741823

Explanation: -2^0 + 2^30 = 1073741824 - 1 = 1073741823, the exact round-trip of toNAF(2^30 - 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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Minimum Sum of Weekly Maximum Costs - Salesforce
  • Solve Two OA Coding Problems - Salesforce (medium)
  • Maximize events attended given date ranges - Salesforce (medium)
  • Implement common data-structure and JS tasks - Salesforce (medium)
  • Implement an LFU cache with O(1) operations - Salesforce (medium)