News Leaflets
A leading news portal.

Check if permutation of N exists with product of atleast 1 subarray’s size and min as K

0 54

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 <bits/stdc++.h>

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)

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! News Leaflets is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Leave a comment