You are given two integers n and maxValue, which are used to describe an ideal array. A 0-indexed integer array arr of length n is considered ideal if the following conditions hold: Every arr[i] is a value from 1 to maxValue, for 0 <= i < n. Every

idealArrays.js

/**
 * @param {number} n
 * @param {number} maxValue
 * @return {number}
 */
// Define the modulo constant for operations
const MODULO = 10n ** 9n + 7n;

// Define the maximum value for calculations
const MAX_VALUE = 10000;

// Initialize an array where each element is a BigInt representation of its index + 1
const STRICT_COUNTS = [Array.from({ length: MAX_VALUE }, (_, i) => BigInt(i + 1))];

let prev_row = Array(MAX_VALUE).fill(1n); // Previous row for counting sequences
let next_row = Array(MAX_VALUE).fill(0n); // Next row for updated counts
let prev_base = 1; // Base multiplier for tracking sequence growth

// Process numbers in power-of-2 increments until reaching MAX_VALUE
while ((prev_base << 1) <= MAX_VALUE) {
  const next_base = prev_base << 1; // Update base to next power of 2

  // Reset next_row values for numbers starting at next_base
  for (let i = next_base - 1; i < MAX_VALUE; i++) {
    next_row[i] = 0n;
  }

  // Populate next_row with counts based on previous numbers
  for (let prev_num = prev_base; prev_num <= MAX_VALUE; prev_num++) {
    const prev_count = prev_row[prev_num - 1];
    
    // Multiply prev_num by increasing factors until exceeding MAX_VALUE
    for (let mult = 2; ; mult++) {
      const product = prev_num * mult;
      if (product > MAX_VALUE) break; // Stop when product surpasses MAX_VALUE
      next_row[product - 1] = (next_row[product - 1] + prev_count) % MODULO; // Update count
    }
  }

  // Generate cumulative counts for current base interval
  const current_counts = Array(MAX_VALUE + 1 - next_base).fill(next_row[next_base - 1]);
  for (let next_num = next_base + 1; next_num <= MAX_VALUE; next_num++) {
    current_counts[next_num - next_base] =
      (current_counts[next_num - 1 - next_base] + next_row[next_num - 1]) % MODULO;
  }

  // Store calculated counts for this base level
  STRICT_COUNTS.push(current_counts);
  prev_base = next_base; // Move to next base level
  [prev_row, next_row] = [next_row, prev_row]; // Swap rows for next iteration
}

// Function to calculate ideal arrays given n and maxValue
var idealArrays = function(n, maxValue) {
    let count = 0n; // Store final count
  let combo = 1n; // Combination factor for computations
  let topFactor = BigInt(n - 1);
  let bottomFactor = 1n;
  let base = 1;

  const maxK = Math.min(n, STRICT_COUNTS.length); // Limit iteration count

  // Iterate through STRICT_COUNTS levels
  for (let k = 0; k < maxK; k++) {
    if (base <= maxValue) {
      const idx = maxValue - base;
      count = (count + combo * STRICT_COUNTS[k][idx]) % MODULO;
    } else {
      break;
    }

    // Update combination values for the next iteration
    combo = (combo * topFactor) / bottomFactor;
    topFactor -= 1n;
    bottomFactor += 1n;
    base <<= 1;
  }

  return Number(count); // Convert BigInt count to a number for final output
};