News Leaflets
0 94

Given two integers N and K, the task is to check if it is possible to form a permutation of N integers such that it contains atleast 1 subarray such that the product of length of that subarray with minimum element present in it is K.

A permutation of size N have all the integers from 1 to N present in it only once.

Examples:

Input: N = 5, K = 6
Output: True
Explanation: {4, 2, 1, 3, 5} is a valid array containing integers from 1 to 5. The required subarray is {3, 5}.
Length of subarray = 2, minimum element in subarray = 3.
Their product = 2 x 3 = 6, which is equal to K.

Input: N = 4, K = 10
Output: False

Approach: The problem can be solved based  on the following observation:

Suppose in a N size array having integers from 1 to N, there exist a subarray of size L, having minimum element M such that M * L = K. Therefore, M = K / L or K must be divisible by the length of the subarray. Also, M should be minimum element in subarray of size L

In a permutation of N integers, there are N – M + 1 elements, which are greater than or equal to M. So, for M to be minimum in subarray of size L, N – M + 1 ≥ L

Follow the steps mentioned below to implement the above idea:

• Iterate the array from i = 1 to N
• Let i be the length of subarray satisfying the required conditions.
• Calculate the minimum element in the subarray.
• As, L * M = K, so, M=K / L, (where M is the minimum element in current subarray)
• Check if conditions stated in observation are satisfied or not i.e. M < N – L + 1.
• If so, return true.

Below is the implementation of the above approach.

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `bool` `isPossible(``int` `N, ``int` `K)` `{` `    ` `    ``bool` `ans = ``true``;` ` `  `    ``for` `(``int` `i = 1; i <= N; i++) {` ` `  `        ` `        ` `        ``int` `length = i;` ` `  `        ` `        ` `        ` `        ` `        ``if` `(K % length == 0) {` ` `  `            ` `            ``int` `min_element = K / length;` ` `  `            ` `            ` `            ` `            ` `            ``if` `(min_element < N - length + 1) {` `                ``ans = ``true``;` `                ``break``;` `            ``}` `        ``}` `    ``}` ` `  `    ` `    ``return` `ans;` `}` ` `  `int` `main()` `{` `    ``int` `N = 5;` `    ``int` `K = 6;` ` `  `    ` `    ``bool` `answer = isPossible(N, K);` `    ``cout << boolalpha << answer;` `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Space: O(1)