Check if there exists any subarray with the given conditions
Given two integers N and X. Then the task is to return YES or NO by checking whether there exists a subarray in any permutation of length N such that it contains a subarray, where A*B is equal to the X. Here A and B denote the number of elements in sub-array and the first element of sorted subarray respectively.
Examples:
Input: N = 5, X = 3
Output: YES
Explanation: Considered the permutation is: {5, 2, 1, 3, 4}. Take the sub-array {A4. . . .A4} = { 3 }. Then A = 1 (As only 1 element is there), B = 3 (If the sub-array is sorted then first element of that sub-array will be 3). So, A * B = 1 * 3 = 3, Which is equal to Y. Therefore, output is YES.Input: N = 7, X = 56
Output: NO
Explanation: It can be verified that no permutation of length N exists such that, It gives value of A * B as 56. Therefore, output is NO.
Approach: To solve the problem follow the below idea:
The problem is based on Greedy logic and observation based. It can be solved by implementing those observations by implementing them in a code. The observation is, there will surely exist a subarray if the condition (X % i == 0 && (X / i) ≥ 1 && (( X / i) ≤ N – i + 1) successfully meet, where i is the current element.
Below are the steps for the above approach:
- Create a Boolean Flag and mark it as False initially.
- Run a for loop from i = 1 to i ≤ N and follow the below-mentioned steps under the scope of the loop:
- If (X % i == 0 && (X / i) ≥ 1 && (( X / i) ≤ N – i + 1) is true then mark the flag as true and break the loop.
- Check if the flag is true, print YES else, print NO.
Below is the code to implement the approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Method for checking whether // SubArray exists or not void SubArrayExists( int N, long X, bool Flag) { // Loop for traversing // from 1 to N for ( int i = 1; i <= N; i++) { // Testing the condition if (X % i == 0 && (X / i) >= 1 && ((X / i) <= N - i + 1)) { // Marking the flag true and // breaking the loop Flag = true ; break ; } } cout << (Flag ? "YES" : "NO" ) << endl; } int main() { // Inputs int N = 5; long X = 3; bool Flag = false ; // Function call SubArrayExists(N, X, Flag); } // This code is contributed by Rahul Bhardwaj @rahulbhardwaj.rb |
Java
import java.util.*; public class GFG { // Driver Function public static void main(String[] args) { // Inputs int N = 5 ; long X = 3 ; Boolean Flag = false ; // Function call SubArrayExists(N, X, Flag); } // Method for checking whether // SubArray exists or not static void SubArrayExists( int N, long X, boolean Flag) { // Loop for traversing // from 1 to N for ( int i = 1 ; i <= N; i++) { // Testing the condition if (X % i == 0 && (X / i) >= 1 && ((X / i) <= N - i + 1 )) { // Marking the flag true and // breaking the loop Flag = true ; break ; } } System.out.println(Flag ? "YES" : "NO" ); } } |
Python3
def subarray_exists(N, X): flag = False # Loop for traversing from 1 to N for i in range ( 1 , N + 1 ): # Testing the condition if X % i = = 0 and (X / / i) > = 1 and ((X / / i) < = N - i + 1 ): # Marking the flag true and breaking the loop flag = True break print ( "YES" if flag else "NO" ) # Inputs N = 5 X = 3 # Function call subarray_exists(N, X) |
C#
// C# code implementation using System; public class GFG { static public void Main() { // Inputs int N = 5; long X = 3; bool Flag = false ; // Function call SubArrayExists(N, X, Flag); } // Method for checking whether SubArray exists or not static void SubArrayExists( int N, long X, bool Flag) { // Loop for traversing from 1 to N for ( int i = 1; i <= N; i++) { // Testing the condition if (X % i == 0 && (X / i) >= 1 && ((X / i) <= N - i + 1)) { // Marking the flag true and breaking the // loop Flag = true ; break ; } } Console.WriteLine(Flag ? "YES" : "NO" ); } } // This code is contributed by sankar. |
Javascript
// JavaScript code to implement the approach function SubArrayExists(N, X) { let Flag = false ; // Loop for traversing from 1 to N for (let i = 1; i <= N; i++) { // Testing the condition if (X % i == 0 && (X / i) >= 1 && ((X / i) <= N - i + 1)) { // Marking the flag true and breaking the loop Flag = true ; break ; } } console.log(Flag ? "YES" : "NO" ); } // Inputs let N = 5; let X = 3; // Function call SubArrayExists(N, X); |
YES
Time Complexity: O(N)
Auxiliary Space: O(1), As no extra space is used.