Given an integer N, the task is to find the MDAS factorial.
The general factorial of a no. N is given by:
Factorial(N) = (N)*(N-1)*(N-2)*(N-3)*(N-4)*(N-5)*(N-6)*(N-7)- – – – – -(3)*(2)*(1).
In MDAS factorial, instead of simply multiplying the numbers from N to 1, we perform four operations, Multiplication(*), Divide(/), Addition(+) and Subtraction(-) in a repeating pattern as shown below:
MDAS_Factorial(N) = (N) * (N-1) / (N-2) + (N-3) – (N-4) – – – – – upto 1.
By using the integers in decreasing order, we swap the multiplication operations for fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in the above order.
Examples:
Input : N = 4 Output : 7 Explanation : MDAS_Factorial(4) = 4 * 3 / 2 + 1 = 7 Input : N = 10 Output : 12 Explanation : MDAS_Factorial(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1 = 12
Simple Approach: The idea is to use a loop for each cycle of operations (*,/,+,-) and calculate the MDAS Factorial of N. But this may work slow if N is very large. The Time Complexity of this approach is O(N).
Efficient Approach:
If we observe carefully it can be concluded that:
- If N is less than or equal to 2 then the answer will be N itself.
- If N is 3 OR N is 4, the answer is N + 3.
- If (N – 4) is completely divisible by 4, the answer is N + 1.
- If (N – 4) gives remainder 1 OR 2 while dividing by 4, the answer is N + 2.
- For the remaining values, the answer will be N – 1.
Below is the implementation of the above approach
C++
// C++ Program to find MDAS_Factorial#include <bits/stdc++.h>using namespace std;// Program to find MDAS_factorialint MDAS_Factorial(int N){ if (N <= 2) return N; if (N <= 4) return (N + 3); if ((N - 4) % 4 == 0) return (N + 1); else if ((N - 4) % 4 <= 2) return (N + 2); else return (N - 1);}// Driver codeint main(){ int N = 4; cout << MDAS_Factorial(N) << endl; N = 10; cout << MDAS_Factorial(N) << endl; return 0;} |
Java
// Java program find MDAS_Factorialimport java.util.*;class Count { public static int MDAS_Factorial(int N) { if (N <= 2) return N; if (N <= 4) return (N + 3); if ((N - 4) % 4 == 0) return (N + 1); else if ((N - 4) % 4 <= 2) return (N + 2); else return (N - 1); } public static void main(String[] args) { int N = 4; System.out.println(MDAS_Factorial(N)); N = 10; System.out.println(MDAS_Factorial(N)); }} |
Python3
# Python3 code find MDAS_Factorialdef MDAS_Factorial( N ): 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# Driver codeN = 4 print(MDAS_Factorial( N ) )N = 10print(MDAS_Factorial( N ) ) |
C#
// C# program to find MDAS_Factorialusing System;class Count { public static int MDAS_Factorial(int N) { if (N <= 2) return N; if (N <= 4) return (N + 3); if ((N - 4) % 4 == 0) return (N + 1); else if ((N - 4) % 4 <= 2) return (N + 2); else return (N - 1); } // Driver code public static void Main() { int N = 4; Console.WriteLine(MDAS_Factorial(N)); N = 10; Console.WriteLine(MDAS_Factorial(N)); }} |
PHP
<?php// PHP Program // Program to find MDAS_factorialfunction MDAS_Factorial($N){ if ($N <= 2) return N; if ($N <= 4) return ($N + 3); if (($N - 4) % 4 == 0) return ($N + 1); else if (($N - 4) % 4 <= 2) return ($N + 2); else return ($N - 1);}// Driver code$N = 4;echo MDAS_Factorial($N);echo("\n");$N = 10;echo MDAS_Factorial($N);?> |
Javascript
// Javascript Program// Program to find MDAS_factorialfunction MDAS_Factorial(N){ if (N <= 2) return N; if (N <= 4) return (N + 3); if ((N - 4) % 4 == 0) return (N + 1); else if ((N - 4) % 4 <= 2) return (N + 2); else return (N - 1);}// Driver codelet N = 4;document.write(MDAS_Factorial(N) + "<br>")N = 10;document.write(MDAS_Factorial(N));// This code is contributed by gfgking |
Output:
7 12
Time complexity: O(1), since no loop is there.
Auxiliary space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
