Subramanya's Digital Garden

Recent Notes

2117. Abbreviating the Product of a Range

3 min read

links: Algorithms MOC

2117. Abbreviating the Product of a Range

You are given two positive integers left and right with left <= right. Calculate the product of all integers in the inclusive range [left, right].

Since the product may be very large, you will abbreviate it following these steps:

  1. Count all trailing zeros in the product and remove them. Let us denote this count as C.
    • For example, there are 3 trailing zeros in 1000, and there are 0 trailing zeros in 546.
  2. Denote the remaining number of digits in the product as d. If d > 10, then express the product as <pre>...<suf> where <pre> denotes the first 5 digits of the product, and <suf> denotes the last 5 digits of the product after removing all trailing zeros. If d <= 10, we keep it unchanged.
    • For example, we express 1234567654321 as 12345...54321, but 1234567 is represented as 1234567.
  3. Finally, represent the product as a string "<pre>...<suf>eC".
    • For example, 12345678987600000 will be represented as "12345...89876e5".

Return a string denoting the abbreviated product of all integers in the inclusive range `[left, right

Constraints:

  • 1 ⇐ left ⇐ right ⇐

Approach 1

  1. A Common sense approach is multiply the number left by incrementing 1 until it reaches right. The problem with this approach is when the number is too large it’s represented in scientific form something like 1.023e4 and we can’t extract last 5 digits and zeroes from it.

Approach 2

  1. To find prefix keep the product between 0 to 1 by dividing it
  2. To find zeroes divide it and increment zero count variable
  3. To find suffix check if suffix is less than . If it’s greater than that divide it with
  4. Keep track of total digits from prefix calculation and zeroes count from suffix calculation.
  5. This can be used to calculate suffix

Code

/**
 * @param {number} left
 * @param {number} right
 * @return {string}
 */
var abbreviateProduct = function(left, right) {
  let product = 1
  let suffix = 1
  let zeroesCount = 0
  let originalDigitsCount = 0
 
  for(let i = left; i <= right; i++) {
    product *= i
    while(product >= 1) {
      product /= 10
      originalDigitsCount += 1
    }
 
    suffix *= i
    while(suffix % 10 == 0) {
      suffix /= 10
      zeroesCount += 1
    }
 
    if(suffix > 10 ** 12) {
      suffix %= 10 ** 12
    }
  }
 
  let digitsCountWithoutZeroes = originalDigitsCount - zeroesCount
  if(digitsCountWithoutZeroes <= 10) {
    return `${parseInt(product * Math.pow(10, digitsCountWithoutZeroes) + 0.5)}e${zeroesCount}`
  } else {
    let suffixString = `0000${suffix}`
    return `${parseInt(product * 100000)}...${suffixString.substring(suffixString.length - 5)}e${zeroesCount}`
  }
}

tags: math

sources:

Graph View