Y
Published on

BigFrontEnd Category 3 BigInt Implementation Questions

Authors
  • avatar
    Name
    Yinhuan Yuan
    Twitter

Introduction

This blog post summarizes the BigInt and BigDecimal implementation questions found on BigFrontEnd.Dev and leetcode.

1.implement BigInt addition

62.https://bigfrontend.dev/problem/add-BigInt-string

Luckily we have BigInt in JavaScript so handle big numbers.

What if we need to do it by ourselves for older browsers?

You are asked to implement a string addition function, with all non-negative integers in string.

add('999999999999999999', '1')
// '1000000000000000000'

Don't use BigInt directly, it is not our goal here.

Solution:

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function add(num1, num2) {
  const n = Math.max(num1.length, num2.length);
  num1 = num1.padStart(n, "0");
  num2 = num2.padStart(n, "0");
  let carry = 0;
  const result = [];
  for (let i = n - 1; i >= 0; i--) {
    const sum = Number(num1[i]) + Number(num2[i]) + carry;
    carry = Math.floor(sum / 10);
    result.unshift(sum % 10);
  }
  if (carry > 0) {
    result.unshift(carry);
  }
  const ans = result.join("").replace(/^0+/, "");
  return ans.length === 0 ? "0" : ans;
}

2.implement BigInt subtraction

75.https://bigfrontend.dev/problem/implement-BigInt-subtraction

Luckily we already have built-in support of BigInt in JavaScript, at least in some browsers.

1000000000000000000000n - 999999999999999999999n
// 1n

Suppose BigInt cannot be used, can you implement a string subtraction function by yourself?

subtract('1000000000000000000000', '999999999999999999999')
// '1'

All input are valid non-negative integer strings, and the result is guaranteed to be non-negative.

Don't use BigInt directly, it is not our goal here

Solution:

/**
 * @param {string} minuend
 * @param {string} subtrahend
 * @return {string}
 */
function subtract(num1, num2) {
  const n = Math.max(num1.length, num2.length);
  num1 = num1.padStart(n, "0");
  num2 = num2.padStart(n, "0");

  let borrow = 0;
  const result = [];
  for (let i = n - 1; i >= 0; i--) {
    const sub = Number(num1[i]) - Number(num2[i]) - borrow;
    borrow = sub < 0 ? 1 : 0;
    result.unshift(sub < 0 ? 10 + sub : sub);
  }
  if (borrow !== 0) {
    throw new Error(`${num1} is less than ${num2}`);
  }
  const ans = result.join("").replace(/^0+/, "");
  return ans.length === 0 ? "0" : ans;
}

3.implement BigInt addition with sign

76.https://bigfrontend.dev/problem/implement-BigInt-addition-with-sign

This is a follow-up on 62. implement BigInt addition.

You are asked to implement a string addition function, with possible negative integers. Also, '+' plus sign should also be supported

add('-999999999999999999', '-1')
// '-1000000000000000000'
add('-999999999999999999', '+1')
// '-999999999999999998'

Don't use BigInt directly, it is not our goal here.

Solution:

const parseNumber = (num) => {
  const sign = num.startsWith("-") ? -1 : 1;
  let value = num;
  if (num.startsWith("-")) value = num.slice(1);
  if (num.startsWith("+")) value = num.slice(1);
  return { sign, value };
};

const compare = (num1, num2) => {
  if (num1.length !== num2.length) {
    return num1.length - num2.length;
  }
  for (let i = 0; i < num1.length; i++) {
    if (num1[i] !== num2[i]) {
      return num1[i] - num2[i];
    }
  }
  return 0;
};

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function add(num1, num2) {
  const { sign: sign1, value: value1 } = parseNumber(num1);
  const { sign: sign2, value: value2 } = parseNumber(num2);
  if (sign1 === sign2) {
    const result = addNumber(value1, value2);
    return sign1 === 1 ? result : "-" + result;
  }
  const greaterOrEqual = compare(value1, value2) >= 0;
  const result = greaterOrEqual
    ? subtractNumber(value1, value2)
    : subtractNumber(value2, value1);
  if (greaterOrEqual) {
    return sign1 === 1 ? result : "-" + result;
  }
  return sign1 === 1 ? "-" + result : result;
}

4.implement BigInt subtraction with sign

77.https://bigfrontend.dev/problem/implement-BigInt-subtraction-with-sign

This is a follow-up on 75. implement BigInt subtraction.

You are asked to implement a string substraction function, with possible negative integers. Also, '+' plus sign should also be supported

substract('-999999999999999999', '-1')
// '-999999999999999998'
substract('-999999999999999999', '+1')
// '-1000000000000000000'

Don't use BigInt directly, it is not our goal here.

Solution:

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function subtract(num1, num2) {
  if (num1 === num2) return "0";
  const { sign: sign1, value: value1 } = parseNumber(num1);
  const { sign: sign2, value: value2 } = parseNumber(num2);
  if (sign1 !== sign2) {
    const result = addNumber(value1, value2);
    return sign1 === 1 ? result : "-" + result;
  }
  const greaterOrEqual = compare(value1, value2) >= 0;
  const result = greaterOrEqual
    ? subtractNumber(value1, value2)
    : subtractNumber(value2, value1);
  if (greaterOrEqual) {
    return sign1 === 1 ? result : "-" + result;
  }
  return sign1 === 1 ? "-" + result : result;
}

5. implement BigInt multiplication

114.https://bigfrontend.dev/problem/implement-BigInt-multiplication

This is a follow-up on 76. implement BigInt addition with sign.

You are asked to create a function that multiplies two big integers in string.

multiply(
  '1123456787654323456789',
  '1234567887654323456'
)
// '1386983673205309924427166592431045142784'

Solution:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function multiply(a, b) {
  const { sign: sign1, value: num1 } = parseNumber(a);
  const { sign: sign2, value: num2 } = parseNumber(b);
  const n = num1.length;
  const m = num2.length;
  const result = Array(n + m).fill(0);
  for (i = n - 1; i >= 0; i--) {
    for (j = m - 1; j >= 0; j--) {
      const mul = Number(num1[i]) * Number(num2[j]) + result[i + j + 1];
      result[i + j + 1] = mul % 10;
      result[i + j] += Math.floor(mul / 10);
    }
  }
  // Remove leading zeros and convert array to string
  let ans = result.join("").replace(/^0+/, "");
  // If the result is an empty string, return '0'
  return ans === "" ? "0" : sign1 === sign2 ? ans : "-" + ans;
}

6. implement BigInt division

115.https://bigfrontend.dev/problem/implement-BigInt-division

This is a follow-up on 114. implement BigInt multiplication.

You are asked to create a BigInt division function.

divide(
  '1123456787654323456789',
  '1234567887654323456'
)
// '910'
divide(
  '-1123456787654323456789',
  '1234567887654323456'
)
// '-910'

Notice the result should be rounded towards 0.

divide(
  '5',
  '2'
)
// '2'
divide(
  '-3',
  '2'
)
// '-1'

Solution:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function divide(a, b) {
  const { sign: sign1, value: dividend } = parseNumber(a);
  const { sign: sign2, value: divisor } = parseNumber(b);

  // Edge case: division by zero
  if (divisor === "0") throw new Error("Division by zero");

  // Edge case: divisor is greater than dividend
  if (compare(dividend, divisor) < 0) return "0";

  // Initialize variables
  let quotient = "";
  let remainder = "";

  for (let i = 0; i < dividend.length; i++) {
    remainder += dividend[i];

    // Find the number of times divisor can fit into the current remainder
    let count = 0;
    while (compare(remainder, divisor) >= 0) {
      remainder = subtractNumber(remainder, divisor);
      count++;
    }

    quotient += String(count);
  }

  // Remove leading zeros from the quotient
  quotient = quotient.replace(/^0+/, "");
  if (quotient === "") return "0";
  return sign1 !== sign2 ? "-" + quotient : quotient;
}

7. BigDecimal addition

126.https://bigfrontend.dev/problem/decimal-addition

As you know, number data type in JavaScript cannot represent (all) float numbers accurately due to binary nature.

For some basic calculations, you might use Number.prototype.toFixed() to overcome this, yet for more extreme cases that requires perfect accuracy, it is not enough.

Proposal of BigDecimal to JavaScript is still at an early stage, before it is adopted, you can use other libraries like Big.js.

In this problem, you are asked to implement the addition of two decimals with arbitrary digits.

add('-999999999999999999', '-1')
// '-1000000000000000000'
add(
  '-999999999999999999.999999999999999999999999999999',
  '1.0000000000000000000000000001')
// '-999999999999999998.999999999999999999999999999899'
add(
  '999999999999999999.9999999999999999999999999999',
  '1.0000000000000000000000000001')
// '1000000000000000001'

This problem covers 76. implement BigInt addition with sign. trailing zeroes in the result should be removed.

Solution:

const processDecimalNumber = (a) => {
  if (!a.includes(".")) a += ".0";
  const sign = a.startsWith("-") ? -1 : 1;
  if (a.startsWith("-")) a = a.slice(1);
  if (a.startsWith("+")) a = a.slice(1);
  const [int, frac] = a.split(".");
  return { sign, int, frac };
};

const normalizeDecimalNumbers = (a, b) => {
  const { sign: signA, int: intA, frac: fracA } = processDecimalNumber(a);
  const { sign: signB, int: intB, frac: fracB } = processDecimalNumber(b);
  const maxFracLength = Math.max(fracA.length, fracB.length);
  const normalizedFracA = fracA.padEnd(maxFracLength, "0");
  const normalizedFracB = fracB.padEnd(maxFracLength, "0");

  // Normalize integer part lengths
  const maxIntLength = Math.max(intA.length, intB.length);
  const normalizedIntA = intA.padStart(maxIntLength, "0");
  const normalizedIntB = intB.padStart(maxIntLength, "0");
  let strA = `${normalizedIntA}${normalizedFracA}`;
  let strB = `${normalizedIntB}${normalizedFracB}`;
  return { signA, signB, strA, strB, maxFracLength };
};

const insertDecimalPoint = (result, maxFracLength) => {
  if (maxFracLength >= result.length) {
    result = result.padStart(maxFracLength + 1, "0");
  }
  const positionFromLeft = result.length - maxFracLength;
  // Split the string into two parts
  const part1 = result.slice(0, positionFromLeft);
  const part2 = result.slice(positionFromLeft);
  // Insert the "." between the two parts
  return part1 + "." + part2;
};

const deNormalizeDecimalNumber = (result, maxFracLength, sign) => {
  let ans = insertDecimalPoint(result, maxFracLength)
    .replace(/0+$/, "")
    .replace(/^0+/, "");
  if (ans.length === 1 && ans[0] === ".") {
    return "0";
  }
  if (ans.length > 1 && ans[ans.length - 1] === ".") {
    ans = ans.slice(0, -1);
  }
  if (ans.length > 1 && ans[0] === ".") {
    ans = `0${ans}`;
  }
  return sign === -1 ? "-" + ans : ans;
};

const calculateSign = (signA, signB, strA, strB) => {
  if (signA === signB) {
    return signA;
  } else {
    if (strA < strB) {
      if (signA === 1) {
        return -1;
      } else {
        return 1;
      }
    } else {
      if (signA === 1) {
        return 1;
      } else {
        return -1;
      }
    }
  }
};

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function add(a, b) {
  let { signA, signB, strA, strB, maxFracLength } = normalizeDecimalNumbers(
    a,
    b,
  );
  if (signA !== signB && strA === strB) return "0";
  const sign = calculateSign(signA, signB, strA, strB);
  if (compare(strA, strB) < 0) {
    [signA, signB] = [signB, signA];
    [strA, strB] = [strB, strA];
  }
  let result = (signA === signB ? addNumber : subtractNumber)(strA, strB);
  return deNormalizeDecimalNumber(result, maxFracLength, sign);
}

8.BigDecimal subtraction

127.https://bigfrontend.dev/problem/bigdecimal-subtraction

This is a follow-up on 126. BigDecimal addition

In this problem, you are asked to implement the subtraction of two decimals with arbitrary digits.

subtract('-999999999999999999', '-1')
// '-999999999999999998'
subtract(
  '-999999999999999999.999999999999999999999999999999',
  '1.0000000000000000000000000001')
// '-1000000000000000001.000000000000000000000000000099'
subtract(
  '999999999999999999.999999999999999999999999999999',
  '-1.000000000000000000000000000001')
// '1000000000000000001'

This problem covers 77. implement BigInt subtraction with sign. trailing zeroes in the result should be removed.

Solution:

const calculateSign = (signA, signB, strA, strB) => {
  if ((signA === 1) & (signB === 1)) {
    if (strA > strB) {
      return 1;
    } else {
      return -1;
    }
  } else if ((signA === 1) & (signB === -1)) {
    return 1;
  } else if ((signA === -1) & (signB === 1)) {
    return -1;
  } else {
    // (signA === -1 & signB === -1)
    if (strA > strB) {
      return -1;
    } else {
      return 1;
    }
  }
};
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
function subtract(num1, num2) {
  let { signA, signB, strA, strB, maxFracLength } = normalizeDecimalNumbers(
    num1,
    num2,
  );
  if (signA === signB && strA === strB) return "0";
  const sign = calculateSign(signA, signB, strA, strB);
  if (compare(strA, strB) < 0) {
    [signA, signB] = [signB, signA];
    [strA, strB] = [strB, strA];
  }
  let result = (signA !== signB ? addNumber : subtractNumber)(strA, strB);
  return deNormalizeDecimalNumber(result, maxFracLength, sign);
}

9.BigDecimal multiplication

128.https://bigfrontend.dev/problem/bigdecimal-multiplication

This is a follow-up on 126. BigDecimal addition

In this problem, you are asked to implement the multiplication of two decimals with arbitrary digits.

multiply(
  '1123456787654323456789',
  '1234567887654323456'
)
// '1386983673205309924427166592431045142784'
multiply(
  '-1123456787654323456789',
  '1234567887654323456.12348'
)
// '-1386983673205309924565891036570601003228.30572'
multiply(
  '-0.12345',
  '-1.6789012'
)
// '0.20726035314'

This problem covers 114. implement BigInt multiplication. trailing zeroes in the result should be removed. Big.js defaults return exponential notation when it is too big, in this problem, don't do that

Solution:

const calculateSign = (signA, signB, strA, strB) => {
  if (signA === signB) {
    return 1;
  } else {
    return -1;
  }
};
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function multiply(a, b) {
  if (a === "0" || b === "0") return "0";
  let { signA, signB, strA, strB, maxFracLength } = normalizeDecimalNumbers(
    a,
    b,
  );
  const sign = calculateSign(signA, signB, strA, strB);
  let result = multipleParts(strA, strB);
  return deNormalizeDecimalNumber(result, 2 * maxFracLength, sign);
}

10.BigDecimal Division

129.https://bigfrontend.dev/problem/bigdecimal-division

This is a follow-up on 126. BigDecimal addition

In this problem, you are asked to implement the division of two decimals with arbitrary digits.

divide( '100000000000000.1', '-0.001' ) // '-100000000000000100' divide( '-0.123', '-0.00971' ) // '12.66735324407826982492' This problem covers 115. implement BigInt division. trailing zeroes in the result should be removed. return the result with max 20 digit fraction part, rest be truncated.

Solution:

const calculateSign = (signA, signB) => {
  if (signA === signB) {
    return 1;
  } else {
    return -1;
  }
};

function divide(a, b) {
  let { signA, signB, strA, strB, maxFracLength } = normalizeDecimalNumbers(
    a,
    b,
  );
  const sign = calculateSign(signA, signB);
  const result = divideParts(
    strA.replace(/^0+/, "") + "0".repeat(20),
    strB.replace(/^0+/, ""),
  );
  return deNormalizeDecimalNumber(result, 20, sign);
}
Discuss on Twitter • View on GitHub