Dev Skill: Another Bigmod Problem

Problem link: Another Bigmod Problem

In this problem, we are given three integers A, B, C; we need to calculate A^B % C.

Solution: We can calculate it by using modular arithmetic. We know

• (a * b) % c = ( (a % c) * (b % c) ) %c 
• (a + b) % c = ( (a % c) + (b % c) ) %c 
• a^b = a * a^(b-1)

So with this we can write this following code to calculate A^B % C

This algorithm is called classical bigmod algorithm. But in this problem, we still have problem. Look at line 9 : x = ( x * x ) % c;

Here, since c can be as large as 10^18, the value of x can be (10^18 - 1 ). When we multiply x with x, it will overflow. For example, try with input a = 10^18 - 1, b = 2, c = 10^18.

So how do we calculate ( x * x ) % c, without overflowing? We use the same divide and conquer approach like above. But this time we will use addition instead of multiplication. It's called bigmultiplication, we will write the function as following:

So finally our full code would look like this:

Dev Skill: Game of MODs

Problem link: Game of MODs

In this problem, we are given an integer n with q queries. Each query we have k integer. We need to calculate the maximum and minimum number can be formed after removing k digits from n. Here the digits won't change their position.

Solution: Some things to observer first.

• If k == size of n (digits), then the answer would be 0 0
• If there are leading zeros, we need to remove them, say we got a number like 000000009. this should be changed to 9.
• If we have only 0 digit, then the answer would be zero

We will use recursion technique for building up our desired result. The idea is that a character among first (k+1) characters must be present in the resultant number. So we pick the first (k+1) smallest or largest depending on the situation. Put it on the result, then recur for remaining characters.
This is done in the legend function below. I used a counter variable for checking whether we are creating maximum or minimum number. Look at line 18 for understanding. Only the change in the index can produce two defferent result. Complexity is O(n), the number of digits. Considering all the cases, queries, complexity would be 100*200*11 = 220000