freeCodeCamp Challenge Guide: 9 billion names of God the integer

Guide
1

9 billion names of God the integer

Solutions

Solution 1 (Click to Show/Hide) 
function numberOfNames(num) {
  // Array of integer partition function values
  const p_n = Array(num + 1).fill(0);
  p_n[0] = 1;
  p_n[1] = 1;
  p_n[2] = 2;
  // Fill with recurrence relation
  // P(n) = Sum_k=1:n (-1)^(k+1)*(P(n-k(3k-1)/2) + P(n-k(3k+1)/2))
  for (let n = 3; n <= num; n++) {
    for (let k = 1; k <= n; k++) {
      const d = n - k*(3*k - 1)/2;
      if (d >= 0) {
        p_n[n] += (-1)**(k + 1)*p_n[d];
      } else {
        break;
      }
      if (d - k >= 0) {
        p_n[n] += (-1)**(k + 1)*p_n[d - k];
      } else {
        break;
      }
    }
  }
  return p_n[num];
}
Solution 2 (Click to Show/Hide) 
// Global variable holding sequence
const partitionSeq = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42];

function partitions(n) {
  // Return early if already computed
  if (n < partitionSeq.length) {
    return partitionSeq[n];
  }
  // Partition function based on Euler's Pentagonal Number Theorem
  const terms = [];
  const termk = [];
  for (let k = 1; k <= n; k++) {
    if (k * (3 * k - 1) / 2 <= n) {
      terms.push(k * (3 * k - 1) / 2);
      termk.push(k);
    }
    if ((k * -1) * ((3 * k * -1) - 1) / 2 <= n) {
      terms.push((k * -1) * ((3 * k * -1) - 1) / 2);
      termk.push(k * -1);
    }
  }
  let partitionValue = 0;
  for (let kk in terms) {
    partitionValue += Math.pow(-1, termk[kk] - 1) * partitions(n - terms[kk]);
  }
  // Return computed value
  return partitionValue;
}

function numberOfNames(num) {
  // Compute extra values, as needed
  for (let i = partitionSeq.length; i <= num; i++) {
    partitionSeq.push(partitions(i));
  }
  // Return requested value
  return partitionSeq[num];
}
1 Like