Normally, 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 * 6 * 5 * 4 * 3 * 2 * 1.
We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.
For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1.  However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.
Additionally, the division that we use is floor division such that 10 * 9 / 8 equals 11.  This guarantees the result is an integer.
Implement the clumsy function as defined above: given an integer N, it returns the clumsy factorial of N.
 
Example 1:
Input: 4
Output: 7
Explanation: 7 = 4 * 3 / 2 + 1

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

 
Note:

1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1  (The answer is guaranteed to fit within a 32-bit integer.)

Difficulty: interview

Starter code:

class Solution:
    def clumsy(self, N: int) -> int:
        

Solutions:
class Solution:
    def clumsy(self, N: int) -> int:
        if N <= 2:
            return N
        if N <= 4:
            return N + 3
        
        if (N - 4) % 4 == 0:
            return N + 1
        elif (N - 4) % 4 <= 2:
            return N + 2
        else:
            return N - 1

class Solution:
    def clumsy(self, N: int) -> int:
        all_nums = [i for i in range(N, 0, -1)]
        prio_nums = []
        for i in range(0, len(all_nums) - 3, 4):
            prio_nums.append((all_nums[i] * all_nums[i + 1]) // all_nums[i + 2])
            prio_nums.append(all_nums[i + 3])
        if N % 4 == 3:
            prio_nums.append((all_nums[-3] * all_nums[-2]) // all_nums[-1])
        elif N % 4 == 2:
            prio_nums.append(all_nums[-2] * all_nums[-1])
        elif N % 4 == 1:
            prio_nums.append(all_nums[-1])
        total = prio_nums[0]
        print(prio_nums)
        for i in range(1, len(prio_nums)):
            if i % 2 != 0:
                total = total + prio_nums[i]
            else:
                total = total - prio_nums[i]
        return total
            


class Solution:
    def clumsy(self, N: int) -> int:
        temp = [i for i in range(N,0,-1)]

        # temp[0] *= -1
        
        if N > 3:
            s = (temp[0]*temp[1]//temp[2]+temp[3])
            for i in range(1,N//4):
                s -= (temp[i*4]*temp[i*4+1]//temp[i*4+2] - temp[i*4+3])
                print(s)
                # print(temp[i*4]*temp[i*4+1]//temp[i*4+2])
            if N % 4 == 3:
                s -= temp[-3] * temp[-2] // temp[-1]
            elif N % 4 == 2:
                s -= temp[-2] * temp[-1]
            elif N % 4 == 1:
                s -= temp[-1]
        
        else:
            s = 0
            if N % 4 == 3:
                s += temp[-3] * temp[-2] // temp[-1]
            elif N % 4 == 2:
                s += temp[-2] * temp[-1]
            elif N % 4 == 1:
                s += temp[-1]

        return s

class Solution:
    def clumsy(self, N: int) -> int:
        count=1
        ans=[N]
        for i in range(N-1,0,-1):
            if count%4==1:
                ans[-1]*=i
            elif count%4==2:
                ans[-1]=int(ans[-1]/i)
            elif count%4==3:
                ans.append(i)
            else:
                ans.append(-i)
            count+=1
        return sum(ans)

class Solution:
    def clumsy(self, N: int) -> int:
        flag=1
        temp=0
        cur=0
        i=1
        for j in range(N,0,-1):
            if(i%4==1):
                cur=flag*j
            elif(i%4==2):
                cur*=j
            elif(i%4==3):
                cur=int(cur/j)
            else:
                cur+=j
                temp+=cur
                flag=-1
                cur=0
            i+=1
        return temp+cur

class Solution:
    def clumsy(self, N: int) -> int:
        numbers = list(range(N + 1))[1:]
        numbers.reverse()
        inter_results = []
        for idx, v in enumerate(numbers):
            if idx % 4 == 0:
                inter_results.append(v)
            elif idx % 4 == 1:
                inter_results[-1] *= v
            elif idx % 4 == 2:
                inter_results[-1] = int(inter_results[-1] / v)
            elif idx % 4 == 3:
                inter_results.append(v)
        # print(inter_results)
        final_results = 0
        for idx, v in enumerate(inter_results):
            if idx == 0:
                final_results += v
            elif idx % 2 == 1:
                final_results += v
            elif idx % 2 == 0:
                final_results -= v
        return final_results

class Solution:
    def clumsy(self, n: int) -> int:
        if n == 1:
            return 1
        arr = []
        temp = 0
        for i in range(n,0,-1):
            if temp == 0 or temp == 3:
                arr.append(i)
            elif temp == 1:
                arr[len(arr)-1] = arr[len(arr)-1]*i
            elif temp == 2:
                arr[len(arr)-1] = arr[len(arr)-1]//i
            temp = (temp+1)%4
        c = arr[0]
        for i in range(1,len(arr)):
            if i%2 == 1:
                c+=arr[i]
            else:
                c-=arr[i]
        return c

class Solution:
    def clumsy(self, N: int) -> int:
        op = 0
        s = N
        N = N - 1
        sum_list = []
        sign_list = [1]
        
        while N > 0:
            if op == 0:
                s = s * N
            elif op == 1:
                s = s // N
            elif op == 2:
                sum_list.append(s)
                sign_list.append(1)
                s = N
            else:
                sum_list.append(s)
                sign_list.append(-1)
                s = N
            
            op = (op + 1) % 4
            N -= 1
            
        sum_list.append(s)
        
        s = 0
        for i, v in enumerate(sign_list):
            s+= sign_list[i] * sum_list[i]

        return s
                
            


class Solution:
    def clumsy(self, N: int) -> int:
        stack = []
        j = -1
        for i in range(N, 0, -1):
            stack.append(i)
            if (j % 4 == 0 or j % 4 == 1 and len(stack) > 1):
                x = stack.pop()
                y = stack.pop()
                if (j % 4 == 0):
                    stack.append(x*y)
                elif (j % 4 == 1):
                    stack.append(y//x)
            j += 1
        res = stack[0]
        for j in range(1,len(stack), 2):
            res += stack[j]
            if (j != len(stack) - 1):
                res -= stack[j+1]
        return res


class Solution:
    def clumsy(self, N: int) -> int:
        result = N
        
        product_part = 0
        sum_part = 0
        
        def g(x):
            return N - x + 1
        
        for i in range(0, ceil(N / 4)):
            nums = list(range(4 * i + 1, min(4 * i + 5, N + 1)))
            
            p = g(nums[0])
            s = 0
            if len(nums) > 1:
                p *= g(nums[1])
            if len(nums) > 2:
                p //= g(nums[2])
            if len(nums) > 3:
                s = g(nums[3])
                
            if i > 0:
                p *= -1
            
            product_part += p
            sum_part += s
        
        return product_part + sum_part

class Solution:
    def clumsy(self, N: int) -> int:
        if N == 1:
            return N
        i = N - 1
        operations = []
        curr = N
        which_op = 0
        while i >= 1:
            
            if which_op == 0:
                curr *= i
                curr = int(curr)
                which_op += 1
            elif which_op == 1:
                curr /= i
                curr = int(curr)
                which_op += 1
            elif which_op == 2:
                operations.append((curr, 2))
                curr = i
                which_op += 1
            elif which_op == 3:
                operations.append((curr, 3))
                which_op = 0
                curr = i
                which_op = 0
            if i == 1:
                operations.append((curr, 0))
            i -= 1
            
        #print(operations)
        sol = 0
        index = 0
        if len(operations) == 1:
            return operations[0][0]
        while index < len(operations) - 1:
            if index == 0:
                sol = operations[index][0]
           
            if operations[index][1] == 2:
                sol+= operations[index + 1][0]
            else:
                sol -= operations[index + 1][0]   
            index+=1
        return sol
            


class Solution:
    def clumsy(self, N: int) -> int:
        res=[]
        danhanvachiachua=False
        i=N
        while i>0:
            if danhanvachiachua==False:
                if i>=3:
                    res.append((i*(i-1))//(i-2))
                elif i==2:
                    res.append(2)
                elif i==1:
                    res.append(1)
                i=i-3
                danhanvachiachua=True
            else:
                res.append(i)
                i=i-1
                danhanvachiachua=False
                
            
        print(res)
        dau=0
        clumsy=res[0]
        for i in range(1,len(res)):
            if dau%2==0:
                clumsy+=res[i]
            else:
                clumsy-=res[i]
            dau+=1
        return clumsy

class Solution:
    def clumsy(self, n):
        
        def helper(arr):
            
            s = arr[0][0]
            
            for i in range(1,len(arr)):
                
                if i%2 != 0:
                    
                    s += arr[i][0]
                    
                else:
                    
                    s -= arr[i][0]
                    
            return s
        
        
        
        
        if n < 2:
            
            return 1
        
        arr = [[n]]
        
        n -= 1
        
        x = 1
        
        while n != 0:
            
            if x == 5:
                
                x = 1
                
            if x == 1:
                
                arr[len(arr) - 1][0] *= n
                
            if x == 2:
                
                arr[len(arr) - 1][0] = int(arr[len(arr) - 1][0]/n)
                
            if x == 3 or x == 4:
                
                arr.append([n])
               
                
            n -= 1
            x += 1
            
        return helper(arr)
                
            
                
            
                
                
                
            
                
            
                
            
                
            


class Solution:
    def clumsy(self, N: int) -> int:
        ans = self.multiplyDivide(N)
        N -= 3
        while N > 0:
            ans += max(N, 0)
            ans -= self.multiplyDivide(N-1)
            N -= 4
        return ans

    def multiplyDivide(self, n: int) -> int:
        return max(0, n) * max(1, n-1) // max(1, n-2)

class Solution:
    def clumsy(self, N: int) -> int:
        fac = [0, 1, 2, 6, 7, 7, 8, 6]
        if N <= 6:
            return fac[N]
        
        for i in range(8, N + 1):
            temp = i * (i - 1) // (i - 2) + (i - 3) - (i - 4) * (i - 5) // (i - 6) * 2 + fac[i - 4]
            fac.append(temp)
        print(fac)
        return fac[-1]

class Solution:
    def clumsy(self, N: int) -> int:
        import functools
        l = list(reversed(list(range(1, N+1))))
        ll= list([z[1] for z in [x for x in enumerate(l) if x[0] %  4 == 0 or x[0] % 4 == 1 or x[0] % 4 == 2]])
        rs = sum(list([z[1] for z in [x for x in enumerate(l) if x[0] % 4 == 3]]))
        pr, acc = [], 1
        for( i, el) in enumerate(ll):
            if i % 3 == 0:acc = el
            elif i % 3 == 1:acc = acc * el
            else: acc = math.floor(acc / el)
            if i %3 == 2 or i == len(ll) -1:
                pr.append(acc)
        # print(l, ll, rs, pr)
        return rs + pr[0] + sum(list([-x for x in pr[1:]]))        


class Solution:
    def clumsy(self, N: int) -> int:
        self.N = N

        k = N // 4
        r = N % 4

        def result(n):        
            if r == 1:
                return 1
            elif r == 2:
                return 2        #2 * 1
            elif r == 3:
                return 6        #3 * 2 // 1
            elif r == 0:
                return 5        #4 * 3 // 2 - 1

        cFac = 2 * (N - 1)
        if N < 4:
            return result(r)
        elif N == 4:
            cFac += 1
        else:
            if r == 0:
                cFac += -4 * (k-2)
            else:
                cFac += -4 * (k-1)
            cFac -= result(r)
        return cFac


class Solution:
    def clumsy(self, N: int) -> int:
        x = ['*', '//', '+', '-'] * (10000//4)
        x = iter(x)
        ans = str(N)
        i = N-1
        while i > 0:
            op = next(x)
            ans += (op+str(i))
            i -= 1
        return eval(ans)
            



class Solution:
    def clumsy(self, N: int) -> int:
        op = ['*', '//', '+', '-']
        op_idx = -1
        idx = N
        result = str(N)
        while idx > 1:
            idx -= 1
            op_idx = (op_idx+1)%4
            result += op[op_idx] + str(idx)
        return eval(result)
            


class Solution:
    def clumsy(self, N: int) -> int:
        res = []
        
        counter = 0
        for num in reversed(list(range(1, N + 1))):
            res.append(str(num))
            if counter == 0:
                res.append('*')
            elif counter == 1:
                res.append('//')
            elif counter == 2:
                res.append('+')
            elif counter == 3:
                res.append('-')
            
            counter += 1
            if counter == 4:
                counter = 0
            
        res.pop()
        
        return eval(''.join(res))


class Solution:
    def clumsy(self, N: int) -> int:
        A = []
        for i in range(N):
            A.append(str(N - i))
            if i % 4 == 0:
                A.append('*')
            elif i % 4 == 1:
                A.append('//')
            elif i % 4 == 2:
                A.append('+')
            else:
                A.append('-')
                
        A.pop()
        return eval(''.join(A))

class Solution:
    def clumsy(self, N: int) -> int:
        res = None
        while N > 0:
            val = N
            N -= 1
            print(N, val, res)
            if N > 0:
                val = val * N
                N -= 1
            print(N, val, res)
            if N > 0:
                val = val // N
                N -= 1
            print(N, val, res)
            if res is None:
                if N > 0:
                    val = val + N
                    N -= 1
                print(N, val, res)
                res = val
            else:
                if N > 0:
                    val = val - N
                    N -= 1
                print(N, val, res)
                res -= val
            print(N, val, res)
        return res

'''
1006. Clumsy Factorial.  Medium

Normally, 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 * 6 * 5 * 4 * 3 * 2 * 1.

We instead make a clumsy factorial: using the integers in decreasing order,
we swap out the multiply operations for a fixed rotation of operations:
multiply (*), divide (/), add (+) and subtract (-) in this order.

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

Additionally, the division that we use is floor division
such that 10 * 9 / 8 equals 11.  This guarantees the result is an integer.

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

Example 1:
Input: 4
Output: 7
Explanation: 7 = 4 * 3 / 2 + 1

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

Note:
1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1  
The answer is guaranteed to fit within a 32-bit integer.

Accepted 11, 010 / 20, 603 submissions.
'''

class SolutionWhile:
    '''
    Runtime: 36 ms, faster than 77.40% of Python3 online submissions for Clumsy Factorial.
    Memory Usage: 14.2 MB, less than 41.24% of Python3 online submissions for Clumsy Factorial.

    Runtime: 40 ms, faster than 68.26% in Python3.
    Memory Usage: 12.8 MB, less than 100.00% in Python3.
    '''
    def clumsy(self, N: int) -> int:
        '''
        1006. Clumsy Factorial
        '''
        R = N
        # set_trace()
        N -= 1
        if N:
            R *= N
            N -= 1
            if N:
                R //= N
                N -= 1
                if N:
                    R += N
                    N -= 1
        while N:
            if N > 2:
                R -= N*(N-1)//(N-2)
                N -= 3
            elif N > 1:
                R -= N*(N-1)
                N -= 2
            elif N > 0:
                R -= N
                N -= 1
            if not N:
                break
            R += N
            N -= 1

        return R

###############################################################################
class Solution:
    pass

Solution = SolutionWhile
# Solution = SolutionMathTricks


'''
1006. Clumsy Factorial.  Medium

Normally, 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 * 6 * 5 * 4 * 3 * 2 * 1.

We instead make a clumsy factorial: using the integers in decreasing order,
we swap out the multiply operations for a fixed rotation of operations:
multiply (*), divide (/), add (+) and subtract (-) in this order.

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

Additionally, the division that we use is floor division
such that 10 * 9 / 8 equals 11.  This guarantees the result is an integer.

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

Example 1:
Input: 4
Output: 7
Explanation: 7 = 4 * 3 / 2 + 1

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

Note:
1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1  
The answer is guaranteed to fit within a 32-bit integer.

Accepted 11, 010 / 20, 603 submissions.
'''

class SolutionWhile:

    def clumsy(self, N: int) -> int:
        '''
        1006. Clumsy Factorial
        Runtime: 40 ms, faster than 68.26% in Python3.
        Memory Usage: 12.8 MB, less than 100.00% in Python3.
        '''
        R = N
        # set_trace()
        N -= 1
        if N:
            R *= N
            N -= 1
            if N:
                R //= N
                N -= 1
                if N:
                    R += N
                    N -= 1
        while N:
            if N > 2:
                R -= N*(N-1)//(N-2)
                N -= 3
            elif N > 1:
                R -= N*(N-1)
                N -= 2
            elif N > 0:
                R -= N
                N -= 1
            if not N:
                break
            R += N
            N -= 1

        return R

###############################################################################
class Solution:
    pass

Solution = SolutionWhile
# Solution = SolutionMathTricks


class Solution:
    def clumsy(self, N: int) -> int:
        
        res = 0
        for i in range(N, 0, -4):
            if i >= 4:
                if i == N:
                    res += i * (i-1) // (i-2) + (i-3)
                else:
                    res -= i * (i-1) // (i-2) - (i-3)
            #print(res)
        
        neg = [1, -1][int(N >= 4)]
        
        if N % 4 == 3:
            res += 6 * neg
        elif N % 4 == 2:
            res += 2 * neg
        elif N % 4 == 1:
            res += 1 * neg
        return int(res)

class Solution:
    def clumsy(self, N: int) -> int:
        return clumsy(N, 1)
        
        
def clumsy(N: int, sign: int) -> int:
    if N == 1:
        return sign * 1
    if N == 2:
        return sign * 2  # sign * 2 * 1
    if N == 3:
        return sign * 6  # sign * 3 * 2 // 1
    if N == 4:
        return sign * 6 + 1  # sign * 4 * 3 // 2 + 1

    return sign * (N * (N-1) // (N-2)) + (N-3) + clumsy(N-4, -1)


# 10 * 9 // 8 + 7 + (-6 * 5 // 4 + 3) + (-2 * 1)
# 11 + 7 - 7 + 3 - 2 == 12


class Solution:
    def clumsy(self, N: int) -> int:
#         if N <= 2:
#             return N
#         if N <= 4:
#             return N + 3
        
#         if (N - 4) % 4 == 0:
#             return N + 1
#         elif (N - 4) % 4 <= 2:
#             return N + 2
#         else:
#             return N - 1
        magic = [1, 2, 2, -1, 0, 0, 3, 3]
        return N + (magic[N % 4] if N > 4 else magic[N + 3])