3 days ago

Delta 2.9k

Hyderabad

 Q1 Help Your Master 

Problem Description

GOAT-master got arrested in a police chase. He is trying to escape the high-tech prison he is held captive in. He needs a pass-code P for disabling all the cameras in order to escape. Passcode is the solution of matrix problem given below. Help him finding the pass-code.
You are given a matrix of order N×N. Each cell in a matrix has a value A : (o<=i,<N), which is either positive or equal to -1 (representing blocked cell)
Cells which are not blocked have distinct values. You can traverse from a cell in any direction (up, down, left or right), if there is no blockage.
For any cell Aj,j, sed-value S;,; is defined as sum of values of cells Ax, y which are multiple of Aj,j, but not reachable from A;,. For blocked cells, sed-value is -1.
Pass-code P is sum of sed-values of all the cells, modulo 1000000007.
Problem Constraints
1<=N<=1e3
1<=A[il [il<=1e6
A[il [j]=-1 for blocked cells only

Input Format

First argument is a 2-D array of integers denoting the above matrix.

Output Format

Return the sum of sed-values of all the cells, modulo 1000000007.
Example Input

Input 1:
[1, 3 ,-1, 5],
[-1,-1, -1 ,-1],
[2, 6 ,-1, 10],
[8, 7 ,- 1 ,11]]
Output 1:
68

Q2  XOR subsequences

Problem Description

You are given an array A, you have to create an array B which is a subsequence of A.
An array B is called valid if it satisfies both the conditions

1. B[i] < B[i+1] where 1 <= i<|B|.
2. bit_count( B[1] ^. ^ B[i-1] ^ B[i]) <= bit_count(B[i+1]) where 1 <= i < |B|.
   .........
   Let X be the Bitwise XOR of all the elements in valid array B.
   You need to find the number of different values of X that can be formed.
   Note: bit_count(t) is the number of set bits present in the binary representation of t

Problem Constraints

1 <= IAl <= 10^5
1 <= A[i] <= 100

Input Format

The first argument is an integer array A

Output Format

Return an integer denoting the number of different values of X that can be formed

Q3 .Space Race 2025

Problem Description

The year is 2025. The space race is in full motion. Elon Musk and Jeff Bezos have already launched their rockets into space. Bill Gates on the other hand, is struggling to even get started However, his good friend Elon, offers him his secret rocket fuel formula if Gates is able to solve a particular problem.

There are A planets Jeff's space company is not very good so he can only jump from the ith planet to the (i+1)th planet and (i+2)th planet. Let XJ be the array of integers representing the number of ways to get to the ith planet if Jeff starts from the 1st planet. XJ[0] would be 1. Since the values can be very large, consider them all modulo 1e9+7

Elon's space company is quite advanced compared to Jeff's. So from the ith planet, Elon's rocket can jump to all planets such that:

•  For every set bit in XJ[i]'s binary representation, Elon's rocket when at the ith planet can jump ahead by values in the range [2^b, 2^bit+2]. •
• Let XII be 5. It's binary representation would be 101. Thus, from the ith planet, Elon's rocket will be able to jump ahead by [2^0, 2^1] u [2^2 2^3] where U is union.
• If i was, let's say, equal to 23 and XJ[i] was equal to 5 then from there, the rocket can jump to all values in these ranges [24, 25) U (27, 31).
  
  Let XEbe the array of integers that denote the number of ways to get to the ith planet using Elon's rocket, starting from the 1st planet. Elon asks you the calculate this array. Since the values can be very large, consider them all modulo 1e9+7. XE[0] = 1

Problem Constraints

1 <= A <= 1e5 

Input Format
The first and only argument is the integer A, denoting the number of planets.

Output Format
Return an array of integers as per the given problem.