freeCodeCamp Challenge Guide: Zeckendorf number representation

freeCodeCamp Community
1

Zeckendorf number representation

Solutions

Solution 1 (Click to Show/Hide) 
function zeckendorf(n) {
  // Validate input
  if (n <= 0) return n.toString();

  // Find nearest Fibonacci
  let f_1 = 1, f_2 = 2;
  while (f_2 < n) {
    [f_1, f_2] = [f_2, f_1 + f_2];
  }

  // Build Fibonacci representation
  let digits = "";
  let remainder = n;
  while (f_1 >= 1) {
    if (f_2 <= remainder) {
      digits += "1";
      remainder -= f_2
    } else {
      digits += "0";
    }
    [f_1, f_2] = [f_2 - f_1, f_1];
  }
  
  return digits[0] === "1" ? digits : digits.slice(1);
}
Solution 2 (Click to Show/Hide) 
function zeckendorf(n) {
  // Validate input
  if (n <= 0) return n.toString();

  // Build Fibonacci list
  const fibonacci = [2, 1];
  while (fibonacci[0] < n) {
    fibonacci.unshift(fibonacci[0] + fibonacci[1]);
  }
  // Build Fibonacci representation
  const digits = fibonacci.reduce((acc, fib) => {
    if (fib <= acc.remainder) {
      acc.remainder -= fib;
      acc.digits += "1";
    } else {
      acc.digits += "0";
    }
    return acc;
  },
  { digits: "", remainder: n })
  .digits;

  return digits[0] === "1" ? digits : digits.slice(1);
}