This question appeared on HackWithInfy 2022

Problem Statement

You are given an array of length N containing a permutation of the first N natural numbers i.e (1 to N). You are able to apply the following operation at most once.

• Choose any subarray of size K and reverse it.

Return the minimum inversions in the array after said operations.

Note — Inversion in an array is defined as a pair of indices (i,j) such that Ai > Aj and i < j.

Constraints

1 <= N <= 5 * 10^3

1 <= A[i] <= N

1 <= K <= N

Sample Test Case — 1

Arr = [1, 2, 3, 4], K = 2

Ans — 0

Explanation

Array initially has 0 inversions. Hence no need to apply any operations.

Sample Test Case — 2

Arr = [4, 3, 5, 1, 2], K = 2

Ans — 6

Explanation

If we reverse the subarray [4, 3], we get Arr = [3, 4, 5, 1, 2].

The resultant inversion is 6. It is the minimum that we can get.

Sample Test Case — 3

Arr = [1, 4, 2, 3, 5], K = 3

Ans — 1

Explanation

If we reverse the subarray [4, 2, 3], we get Arr = [1, 3, 2, 4, 5].

The resultant inversion is 1. It is the minimum that we can get.

Can anyone solve this problem ???

This question appeared on Scaler CodeX 2.0 dated 06-02-22.

Statement

You are given 'N', the size of array where each element in array is Ai = i for each (1 <= i <= N). We have to exactly 'N-1' operations on this array. In each operation, we delete the last element in the array and move the second last element to the front of the array. After completion of all operations, find the remaining number in the array.

Constraints

1 <= N <= 1e9

Sample Test Case — 1

Input -> N = 5

Output -> 4

Explanation

• Initial Array -> [1, 2, 3, 4, 5]

• Operation 1 -> [4, 1, 2, 3] (Delete 5, then array is [1, 2, 3, 4] and move 4 to front of array getting [4, 1, 2, 3])

• Operation 2 -> [2, 4, 1] (Delete 3, then array is [4, 1, 2] and move 2 to front of array getting [2, 4, 1])

• Operation 3 -> [4, 2]

• Operation 4 -> [4]

Sample Test Case — 2

Input -> N = 6

Output -> 3

Explanation

• Initial Array -> [1, 2, 3, 4, 5, 6]

• Operation 1 -> [5, 1, 2, 3, 4] (Delete 6, then array is [1, 2, 3, 4, 5] and move 5 to front of array getting [5, 1, 2, 3, 4])

• Operation 2 -> [3, 5, 1, 2] (Delete 4, then array is [5, 1, 2, 3] and move 3 to front of array getting [3, 5, 1, 2])

• Operation 3 -> [1, 3, 5]

• Operation 4 -> [3, 1]

• Operation 5 -> [3]

Can anyone solve this problem ???

Ode 2 Code 2021 Round-3

Round 3 of Ode 2 Code gave only one question with a total time of 45 mins to solve it. I was not able to solve this problem. Can anyone help me ? PS :- The competition is already over, hence it the question can be disclosed now

Question Statement

You are given

• An array A of N integers.

• And M queries consist of three integers k, y and x.

Beauty of a array A[1], A[2], A[3], A[4],...., A[N] is defined as A[1] + A[2] + A[3] + A[4] + .... + A[N].

For each query, k, y, x, you are given the following conditions :-

• Let U be the bitwise AND of the beauties of any y subarrays among all subarrays of size k.

• And, Z = U | x, where | is the bitwise OR operation.

Calculate the maximum possible value of Z for all queries.

Constraints

• 1 <= N <= 1000

• 1 <= M <= 1000

• 1 <= Ai <= 10^9

• 1 <= ki <= N

• 1 <= yi <= N-ki+1

• 1 <= xi <= 10^9

Sample Test Cases

1) Sample Case 1

N = 5

M = 2

A = [1, 2, 3, 4, 5]

Q = [[2, 3, 9], [3, 2, 17]]

Approach

For the first query

• We have 4 subarrays [1, 2], [2, 3], [3, 4], [4, 5] with beauties 3, 5, 7, 9 respectively.

• You can select bitwise AND of 3 beauties, i.e 3 & 5 & 7 = 1, so U = 1.

• Z = (1 | 9) = 9. This is the maximum possible.

For the second query

• We have 4 subarrays [1, 2, 3], [2, 3, 4], [3, 4, 5] with beauties 6, 9, 12 respectively.

• You can select bitwise AND of 2 beauties, i.e 9 & 12 = 8, so U = 8.

• Z = (8 | 17) = 25. This is the maximum possible.

2) Sample Case 2

N = 5

M = 2

A = [5, 4, 2, 4, 9]

Q = [[2, 2, 7], [2, 3, 6]]

Approach

For the first query

• We have 4 subarrays [5, 4], [4, 2], [2, 4], [4, 9] with beauties 9, 6, 6, 13 respectively.

• You can select bitwise AND of 2 beauties, i.e 9 & 13 = 9, so U = 9.

• Z = (9 | 7) = 15. This is the maximum possible.

For the second query

• We have 4 subarrays [5, 4], [4, 2], [2, 4], [4, 9] with beauties 9, 6, 6, 13 respectively.

• You can select bitwise AND of 3 beauties, i.e 6 & 6 & 13 = 4, so U = 4.

• Z = (4 | 6) = 6. This is the maximum possible.

Please look into this problem.