fork download
copy 
  1. /**
  2.  * Count total clap digits between two numbers a and b.
  3.  * Uses prefix sum technique: f(b) - f(a - 1)
  4.  * @param {number} a
  5.  * @param {number} b
  6.  * @returns {number}
  7.  */
  8. function countClapsInRange(a, b) {
  9. 	if (a > b) return 0;
  10.     /**
  11.      * Count the total number of digits 3, 6, or 9 appearing in numbers from 1 to n.
  12.      * This uses Digit DP: digit-by-digit DFS + memoization.
  13.      */
  14.     function countTotalClapsUpTo(n) {
  15.         const digits = n.toString();
  16.         const memo = new Map();
  17.  
  18.         // Set of digits that represent a "clap" in the 369 game
  19.         const clapDigits = new Set([3, 6, 9]);
  20.  
  21.         /**
  22.          * Recursive function to count claps digit by digit
  23.          * @param {number} digitIndex - Current digit position (from left to right)
  24.          * @param {number} clapCount - Number of clap digits seen so far
  25.          * @param {boolean} isLimited - True if current digit must not exceed original number
  26.          * @returns {number} - Total claps accumulated from this position onward
  27.          */
  28.         function countClapsByDigit(digitIndex, clapCount, isLimited) {
  29.             // Use memoization to avoid recomputing overlapping sub problems
  30.             const memoKey = `${digitIndex},${clapCount},${isLimited}`;
  31.             if (memo.has(memoKey)) return memo.get(memoKey);
  32.  
  33.             // Base case: reached the end of number
  34.             if (digitIndex === digits.length) return clapCount;
  35.  
  36.             // Determine the highest digit can use at this position
  37.             const maxDigit = isLimited ? Number(digits[digitIndex]) : 9;
  38.             let total = 0;
  39.  
  40.             // Try all possible digits at this position
  41.             for (let digit = 0; digit <= maxDigit; digit++) {
  42.                 // If current digit == maxDigit and still limited, let remain limited
  43.                 const nextIsLimited = isLimited && (digit === maxDigit);
  44.  
  45.                 // Add 1 to clap count if current digit is 3, 6, or 9
  46.                 const nextClapCount = clapCount + (clapDigits.has(digit) ? 1 : 0);
  47.  
  48.                 // Recurse to next digit
  49.                 total += countClapsByDigit(
  50.                     digitIndex + 1,
  51.                     nextClapCount,
  52.                     nextIsLimited
  53.                 );
  54.             }
  55.  
  56.             // Memoize the result for this state
  57.             memo.set(memoKey, total);
  58.             return total;
  59.         }
  60.  
  61.         // Start recursion from the first digit, with 0 clap digits, and tight constraint
  62.         return countClapsByDigit(0, 0, true);
  63.     }
  64.  
  65.     return countTotalClapsUpTo(b) - countTotalClapsUpTo(a - 1);
  66. }
  67. let input = '';
  68. process.stdin.on('data', function (chunk) {
  69.     input += chunk;
  70. });
  71.  
  72. process.stdin.on('end', function () {
  73.     const lines = input.trim().split('\n');
  74.     for (const line of lines) {
  75.         const [a, b] = line.trim().split(/\s+/).map(Number);
  76.         console.log(countClapsInRange(a, b));
  77.     }
  78. });
  79.  
Success #stdin #stdout 0.06s 43624KB
comments (?)
stdin
copy 
20 1
-1 3
6 6
1 20
1 40
999999 10000000
999999 100000000
stdout
copy 
0
1
1
6
22
19200006
238200006
https://ideone.com/43XKit
Ewoosoft - Vu Van Nhan - Prob 369
language:
Node.js (node 20.14)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!