Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Array Snap

Hard

0/120

Average time to solve is 45m

Contributed by

0 upvote

Problem statement

Ninja came across this exciting operation called Array Snap.

We can perform Array Snap on an array ‘X’ as follows:

Take any prefix of ‘X’ of any length and append it to the end. But the length of the prefix must not be ‘0’, and the prefix must not be equal to ‘X’.

For example ‘X’ = [2, 3, 1, 5, 6] and we want to perform array snap for prefix of length 3 then ‘X’ after operation will be [5, 6, 2, 3, 1].

Ninja has two arrays, ‘A’ and ‘B’, both of length ‘N’, determining how many different ways to transform ‘A’ into ‘B’ using Array Snap operation exactly ‘K’ times on ‘A’. The answer can be huge, so return it modulo 10^9+7.

Two ways are considered different if the order of applied operations differs. We can say that the two ways are different if there exists an ‘i’ such that (1 <= ‘i’ <= ‘K’) for the first way, we use the prefix of length ‘r’, and for the second way, we use the prefix of length ‘s’ and ‘r’ != ‘s’.

Example :

‘N’ = 3, ‘A’ = [1, 2, 1], ‘B’ = [2, 1, 1], ‘K’ = 2
Only, 1 way to transform ‘A’ into ‘B’.

‘A’ = [1, 2, 1], select prefix of length 2 for array snap.
After 1st operation:
‘A’ = [1, 1, 2], select prefix of length 2 for array snap.
After 2nd operation:
‘A’ = [2, 1, 1].
This is the only possible way to transform ‘A’ into ‘B’.
Hence, the answer is 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains two single space-separated integers, ‘N' and ‘K’.
Each test case's second and third line contains ‘N’ single space-separated integers representing ‘A’ and ‘B’.

Output Format :

For each test case, return the number of ways to transform ‘A’ into ‘B’ modulo 10^9+7.

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ N ≤ 1000    
0 ≤ A[i], B[i] ≤ 10^9
0 ≤ K ≤ 10^5
It’s guaranteed that the sum of K over all the test cases does not exceed 10^5.
It’s guaranteed that the sum of N over all the test cases does not exceed 1000.

Time limit: 1 sec

Sample Input 1 :

2
2 9
1 2
2 1
6 1
1 2 7 1 2 7
2 7 1 2 7 1

Sample Output 1 :

1
2

Explanation For Sample Input 1 :

For test case 1: 
‘A’ = [1, 2], ‘B’ = [2, 1], ‘K’ = 1.
There is only one way to transform ‘A’ into ‘B’ using one array snap operation, and that is by performing an array snap-on prefix of length one on ‘A’.
Hence, the answer is 1.

For test case 2:
‘A’ = [1, 2, 7, 1, 2, 7], ‘B’ = [2, 7, 1, 2, 7, 1], ‘K’ = 1.
Here, there are two ways we can either perform array snap on the prefix of length one or the prefix of length 4.
‘A’ after array snap-on prefix of length one will be [2, 7, 1, 2, 7, 1].
‘A’ after array snap-on prefix of length four will also be the same.

Sample Input 2 :

Sample Output 2 :

1
0

Hint 1

Hint 2

Hint 3

How can we check if we can ever transform ‘A’ into ‘B’ with any number of operations?

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursive Approach

Approach:

We can transform ‘A’ into ‘B’ if they are both cyclic shifts, and the Array Snap operation works as just a cyclic shift of an array.
Even if you perform multiple cyclic shift operations on ‘A’, it will always remain cyclic shift of its initial version. You can come back to ‘A’ after performing some operations.
Let's call some cyclic shift of ‘A’ good if it equals ‘B’ and all the other cyclic shifts bad.
To calculate the number of good and bad shifts, we can use brute force to generate all ‘N’ cyclic shifts of ‘A’ and compare each one with ‘B’.
To generate all cyclic shifts:-
- Create an array in which we will create our current cyclic shift.
- Fix the starting point of cyclic shift.
- Then, fill the array until the size is ‘N’ by traversing array ‘A’ from the starting point, and if we get to the last element, we should go to the first element cyclically.
- Finally, compare our generated array with ‘B’. If they match, then the current cyclic shift is good.
Let the number of good & bad shifts be called ‘goodShifts’ and ‘badShifts’.
Now, we can solve this problem using recursion. We have two possible states of array ‘A’, good or bad, and we must perform precisely ‘K’ operations.
We can map the state of array ‘A’ with a boolean variable true for good and false for bad. Note that 1 represents true and 0 represents false.
Let ‘F(i,j)’ denote the number of ways to get to state ‘j’ by performing ‘i’ operations.
So, ‘F(K, 1)’ will be the number of ways to transform ‘A’ into ‘B’ after ‘K’ operations.
- We can transform our current cyclic shift into any other cyclic shift except itself. So, total ‘N-1’ transformations are possible.
- The recurrence relation will be as follows.
- ‘F(K,1) = F(K-1,0)*(goodShifts) + F(K-1,1)*(goodShift-1)
- ‘F(K,0) = F(K-1,0)*(badShift-1) + F(K-1,1)*(badShift)
- We are doing -1 because we cannot transform string into itself.
Also, we need to take modulo 10^9+7 so that answers don’t go beyond the integer range.

Algorithm:

Declare two variables ‘goodShift’ = 0 and ‘badShift’ = 0.
Iterate the starting point for every cycle from [‘1’, ‘n’] to calculate good and bad shifts.
- Make an array from this starting point until it has ‘n’ elements. Keep adding the next element of array ‘a’. Once we get to the Nth element, take the pointer back to the first element.
- Suppose this created array equals ‘b’, increment ‘goodShift’. Else increment ‘badShift’.
Create a helper function:-
- waysToTransformHelper(‘i’, ‘s’, ‘g’, ‘bs’, ‘u’, ‘mod’).
- ‘i’ represents the number of operations performed.
- ‘s’ represents the current state of array ‘A’. (True or False)
- ‘g’ represents the number of good shifts.
- ‘bs’ represents the number of bad shifts.
- ‘u’ represents the initial state of ‘A’.
- ‘mod’ is the given value 10^9+7.
- This will help us solve problems recursively.
if ‘i’ == 0 return 1 if ‘u’ is same as ‘s’ else 0.
Declare a variable, call it ‘m’ and equate it to ‘goodShift’ if ‘s’ is true or equal to ‘badShift’.
The recursive call will be as follow:
return (waysToTransformHelper(‘i-1’, ‘s’, ‘g’, ‘bs’, ‘u’, ‘mod’)*(‘m’-1))%‘mod’ + (waysToTransformHelper(‘i-1’, ‘!s’, ‘g’, ‘bs’, ‘u’, ‘mod’)*‘m’)%‘mod’.
- ‘!s’ denotes negation of ‘s’.
In the main function, we will call waysToTransformHelper(‘k’, ’1’, ‘goodShift’, ‘badShift’, ‘u’,’ 10^9+7) and return this value.

Time Complexity

O(4^K + N*N), ‘K’ is the number of operations to perform, and ‘N’ is the length of the given array.

We are making four recursive calls on every call. This will make the branching factor of our recursive tree four, and in the worst case, the height of our tree will be ‘K’ and ‘N*N’ for calculating the number of good and bad shifts.

Hence, the time complexity is O(4^K + N*N).

Space Complexity

O(K + N), ‘K’ is the number of operations to perform, and ‘N’ is the length of the given array.

Only ‘K’ calls will be stacked in our function at any given moment because that is the height of our recursive tree.

Hence, the space complexity is O(K + N).

(100% EXP penalty)

Array Snap

Codestudio

Interview problems

Discussion thread on Interview Problem | Array Snap

Hey everyone, creating this thread to discuss the interview problem - Array Snap.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Array Snap

127 views

1 reply

0 upvotes

Console