Intuition
The intuition is going to be very straightforward; We will use the brute force method to solve this problem, we will keep calculating the answer for any ith room using (i - 1)th room using the formula:
No of particles in ith room = i * (Number of particles in (i - 1)th room).
Thus we can simply find the no of particles in Kth room.
Things will become more clear from the following code.
Code
#include <bits/stdc++.h>
using namespace std;
#define mod 10000007
int main()
{
/*'x' is the number of particles present in room 0 */
int k, x;
cin >> k >> x;
/*For looping over 'k' particles */
int i = 1;
/*To store our final answer */
int ans;
while (i <= k)
{
ans = ((i % mod) *(x % mod)) % mod;
/*Now, this will store number of particles in (i - 1)th room*/
x = ans;
i++;
}
cout << ans;
return 0;
}
Input
3 1
Output
6
Complexities
Time Complexity
O(K), where ‘K’ is given in input.
Reason: As we are looping over K rooms and for each room, we are doing the operation in O(1) time; Thus, the overall time complexity to O(1) * O(K) ~ O(K).
Space Complexity
O(1)
Reason: We are not using any external space.
FAQs
-
What is Number Theory?
The pure branch of mathematics that deals with the study of integers and integer-valued functions is known as the number theory.
-
What are the different parts of Number Theory?
Number theory is a vast topic and consists of a large number of topics. Some of them are Prime numbers, Combinatorics as well as advanced topics such as Modular Exponentiation, Fermat's Little Theorem, Wilson's Theorem, Chinese Remainder Theorem, Euler Totient Function, Matrix Exponentiation, etc.
-
How to find the divisors of a factorial?
Steps to find the divisors of a factorial:
First, find the factorial of the given number.
Then, count the total number of divisors of the factorial.
-
What is meant by sieve?
The term "sieve" refers to a method or equipment for separating desired from undesired elements. For example, with a set of numbers, we find the prime numbers and ignore the composite numbers.
-
What are the advantages of using the sieve of Eratosthenes?
a) It is a highly optimized and effective algorithm for determining the prime numbers in a given range.
b) It has low implementation.
Key Takeaways
We saw how we solved the problem ‘Ninja and Chain', which was based on Number Theory. Some other problems that revolve around the number theory concepts are Finding Power of Factorial Divisor, Count Prime in Ranges. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more.
Till then, Happy Coding!
39+ registered 