HACKERRANK: Power Of Large Numbers

Link:- https://www.hackerrank.com/challenges/power-of-large-numbers

Summary:
Given A and B.
Find (A^B)%(10^9+7)

Constraints:
1 <= T <= 10 
1 <= A,B <= 10100000 
A % (109 + 7) != 0

For Example:
Sample Input:
4
3 2
4 5
7 4
34534985349875439875439875349875  93475349759384754395743975349573495

Sample Output:
9
1024
2401
735851262

Logic:
(A^B)%MOD = (A%MOD)^B
Since A is very very large number can't be stored in int or long so using modulo technique bring A in the range of int or long as:
Let 'a' be an array contains digit of A so to construct A%MOD. Let A = 0
for i 0 to len(a):
    A = (A*10 + a[i])%MOD
This gives A%MOD

Now B is also very very large but we can't apply same technique as we done in A as
(A%MOD)^B%MOD != (A%MOD)^(B%MOD)%MOD
So we use Fermet's Little Theorem which says:

where p is prime number.
divide by a both side


Since MOD = 10^9+7 is a prime number

we need to find A^B%MOD
so if  B is divisible by (p-1) or (MOD-1) then B = (MOD-1)*x
so (A^((MOD-1)*x))%MOD = (A^(MOD-1)%MOD)^x%MOD = 1^x%MOD = 1

and if B is not divisible by (MOD-1) then B = (MOD-1)*x + y
so
(A^((MOD-1)*x+y))%MOD = ((A^(MOD-1)%MOD)^x)%MOD*(a^y)%MOD =  1^x*(a^y)%MOD
and y = B%(MOD-1)
so y can be computed as:
y = 0
b is an array contains digit of number B.
for i 0 to len(b)
    y = (y*10 + b[i])%(MOD-1)
if y==0
answer = 1
else
answer = A^y%MOD

To View My Solution:
https://github.com/shivam04/codes/blob/master/hackerrank/math/number%20theory/medium/power-of-large-number.py

CODEFORCES: Sereja and Suffixes(368B)

Problem Link: http://codeforces.com/problemset/problem/368/B

Summary:
Given 'n' number of elements in array.

Given 'm' i.e 'm' different queries each query contains an integer 'l'.

Find the number of distinct elements from 'l' to 'n'  in array.

For Example:

input

10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

output

6
6
6
6
6
5
4
3
2
1

Topic:
Dynamic Programming
Logic:

Let dp[i] be the answer i.e number of distinct elements from i to n.

and dp[i] = dp[i+1] +1 when element at a[i] has not been visited yet or visit[a[i]] = 0 otherwise dp[i] = dp[i+1] i.e visit[a[i]] = 1

For any 'l' print dp[l]  is the answer.

To View my solution:

https://github.com/shivam04/codes/blob/master/codeforces/seerja_and_suffixes.py

HACKER RANK: Journey to the Moon

Problem Link: https://www.hackerrank.com/challenges/journey-to-the-moon

Summary:

There are  trained astronauts numbered from  to . But those in charge of the mission did not receive information about the citizenship of each astronaut. The only information they have is that some particular pairs of astronauts belong to the same country.

Your task is to compute in how many ways they can pick a pair of astronauts belonging to different countries. Assume that you are provided enough pairs to let you identify the groups of astronauts even though you might not know their country directly. For instance, if  are astronauts from the same country; it is sufficient to mention that  and  are pairs of astronauts from the same country without providing information about a third pair .

Print An integer that denotes the number of permissible ways to choose a pair of astronauts.

For Example:

Sample Input:

4 2
0 1
2 3

Sample Output:

4

Topic:

Graph Theory, BFS(Breadth First Search)

Logic:

I have create an adjacency list.

Then Using BFS I have count total number of sub graphs in a graph such that there is no edges between sub graphs and also count total number of nodes in each sub graph.

Then compute number of ways 2 astronauts from different country can be sent to Moon.

For example:

Like From America There are 3 trained astronauts.

From India There are 4 trained astronauts.

From Japan There are 2 trained astronauts.

From China, Australia and Russia There are Only One astronaut.

So number_of_ways = 3*(4+2+1+1+1) + 4*(2+1+1+1) + 2*(1+1+1) + 2 + 1 = 56

To View My Solution:

https://github.com/shivam04/codes/blob/master/hackerrank/algo/graph/medium/journey-to-the-moon.py