Topic describes

Original problem link: stupid factorial

In general, the factorial of a positive integer n is the product of all positive integers less than or equal to n. For example, factorial(10) = 10 _ 9 _ 8 _ 7 _ 5 _ 4 _ 2 * 1.

Instead, we designed a clumsy factorial: in a descending sequence of integers, we replaced the original multiplication operators in turn with a fixed sequence of operators: multiplication (*), division (/), addition (+), and subtraction (-).

For example, clumsy(10) = 10 _ 9/8 + 7-6 _ 5/4 + 3-2 * 1. However, these operations still use the usual arithmetic order: we perform all the multiplication and division steps before any addition or subtraction steps, and process the multiplication and division steps from left to right.

Also, the division we’re using is floor division, so 10 times 9/8 is 11. This guarantees that the result is an integer.

Implement the stupid function defined above: given an integer N, it returns the stupid factorial of N.

The sample

Input:10Output:12Explanation:12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1
Copy the code

answer

Method a

In fact, it is not so complicated. A simple solution is to group every four numbers into a group for operation. If the last remaining number is less than four, special treatment will be made:

var clumsy = function (N) {
  if (N <= 2) return N
  if (N === 3) return 6
  let sum = ~~((N * (N - 1)) / (N - 2)) + N - 3
  N -= 4
  while (N >= 4) {
    sum += -~~((N * (N - 1)) / (N - 2)) + N - 3
    N -= 4
  }
  return sum - clumsy(N)
}
Copy the code

Complexity analysis:

  • Time complexity: O(N), traversal N numbers
  • Space complexity: O(1), using only constant temporary variables

Method 2

In this case, the priority of multiplication and division is higher than that of addition and subtraction. Therefore, we can use the stack method. When we meet multiplication and division, the two numbers at the top of the stack are removed and combined.

var clumsy = function (N) {
  const stack = [N--]
  let index = 0
  while (N) {
    if (index % 4= = =0) {
      stack.push(N * stack.pop())
    } else if (index % 4= = =1) {
      stack.push(~~(stack.pop() / N))
    } else if (index % 4= = =2) {
      stack.push(N)
    } else {
      stack.push(-N)
    }
    N--
    index++
  }
  return stack.reduce((total, next) = > total + next, 0)}Copy the code

Complexity analysis:

  • Time complexity: O(N), traversal N numbers
  • Space complexity: O(1), using only constant temporary variables