1.
Introduction
2.
Understanding the Problem
2.1.
Example
3.
Intuition
3.1.
Code
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Ninja and Chains

Saksham Gupta
0 upvote

## Introduction

Maths is a very fun subject to study, and so is programming, but what happens when these two are combined? Today, we will discuss one such problem, i.e., Ninja and Chains, where your concepts related to programming and maths would be judged. Now let's see the problem statement in detail.

## Understanding the Problem

• Ninja is working very hard in his laboratory. His laboratory has infinite rooms, and Kth rooms are connected to room number K-1. Now the number of particles in any room depends on the K-1 chamber and is equal to K times the number of particles present in room K-1. We have been given the number of particles present in room number 0, and our task is to find the number of particles in the Kth room as the value of the answer can be very large return it by taking mod of it.

Let's understand this by the following example.

### Example

Input

K =  [3]
Number of particles in 0th room = 1

Output

6

Explanation

The number of particles in room 0 is 1, then the number of particles in room 1 will be 1 * 1 = 1.
For room number 2 there will be 2 * 1 = 2 particles.
For room number 3 there will be 3 * 2 = 6 particles; thus, our output will be 6.

Also see, Euclid GCD Algorithm

## 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;
}

3 1

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

1. 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.

2. 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.

3. 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.

4. 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.

5. 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 DivisorCount 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!

Live masterclass