Question Name:Discover the Monk

Solution :

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,q;
    cin>>n>>q;
    ll a[n];
    for(ll i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    while(q--)
    {
        ll key;
        cin>>key;
        ll low=0;
        ll high =n-1;
        ll flag=0;
        while(low<=high)
        {
           ll mid = (low + high) /2;
           if(a[mid]<key)
           {
             low=mid+1;
           }
           else if(a[mid]>key)
           {
              high=mid-1;
           }
          else
            { flag=1;
            break;
        }
        }
        if(flag==1)
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
         
    }
    return 0;
}

Problem Name: Discover the Monk

The "Discover the Monk" problem involves checking if a given element exists in an array for multiple queries. For each query, you are given an integer $X$ and you need to determine if $X$ exists in the array. The goal is to do this efficiently due to the constraints.

Problem Breakdown

Input Details:

N: The size of the array $A$ .
Q: The number of queries.
The second line contains $N$ integers representing the elements of the array $A$ .
The next $Q$ lines each contain a single integer $X$ , which is the target number you need to search for in the array $A$ .

Output:

For each query, you must print "YES" if $X$ exists in the array, and "NO" if it doesn't.

Constraints

$1 \leq N, Q \leq 10^5$
$1 \leq A[i], X \leq 10^9$

Solution Strategy

Given the constraints (up to $10^5$ elements in the array and $10^5$ queries), a brute-force linear search for each query would be inefficient. Instead, you can:

Sort the array.
Use binary search for each query to check if the element $X$ is present.

Binary search is efficient because it runs in $O(\log N)$ , and sorting the array takes $O(N \log N)$ . For each query, binary search can find if the number exists in $O(\log N)$ , making the approach much faster than a linear search.

Step-by-Step Explanation

Input Parsing:
- Read $N$ (size of the array) and $Q$ (number of queries).
- Read the array $A$ .
- Sort the array $A$ to allow for binary search.
Binary Search:
- For each query, use binary search to check if the queried element $X$ exists in $A$ . This is done using a simple iterative approach or functions like std::binary_search in C++.
Output:
- If the element is found during the binary search, output "YES".
- Otherwise, output "NO".

Code Walkthrough


#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main() {
    ios_base::sync_with_stdio(false); // To optimize I/O
    cin.tie(NULL); // Unnecessary synchronization with C-style I/O is disabled

    ll n, q; // n: size of array, q: number of queries
    cin >> n >> q; 
    
    ll a[n]; // Array to hold elements
    for(ll i = 0; i < n; i++) {
        cin >> a[i]; // Read array elements
    }
    
    // Sorting the array to prepare for binary search
    sort(a, a + n);

    // Processing each query
    while(q--) {
        ll key; // Query number (key)
        cin >> key;
        
        // Binary search algorithm
        ll low = 0;
        ll high = n - 1;
        ll flag = 0; // Flag to indicate if the key was found
        
        // Perform binary search
        while(low <= high) {
            ll mid = (low + high) / 2;
            if(a[mid] < key) {
                low = mid + 1; // Search in the right half
            } else if(a[mid] > key) {
                high = mid - 1; // Search in the left half
            } else {
                flag = 1; // Key found
                break;
            }
        }
        
        // Output the result for the current query
        if(flag == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    
    return 0; // Return success
}

Detailed Explanation of Code

Input Parsing and Sorting:
- The input begins by reading $n$ (the number of elements in the array) and $q$ (the number of queries).
- The array $A$ is then read and sorted in ascending order to facilitate binary search.
Binary Search:
- For each query, the code reads the value $X$ (the target) and performs a binary search within the sorted array.
- The binary search works by comparing the middle element with the target. If the middle element is smaller than the target, we move to the right half of the array. If it's larger, we move to the left half. If the target is found, we set a flag and break the loop.
Output:
- If the flag is set, indicating that the target was found, the program prints "YES".
- Otherwise, it prints "NO".

Time Complexity Analysis

Sorting the array: $O(N \log N)$ .
Binary search for each query: $O(\log N)$ . For $Q$ queries, this becomes $O(Q \log N)$ .

Thus, the total time complexity of the solution is $O(N \log N + Q \log N)$ , which is efficient enough given the problem constraints.

Example Walkthrough

Test Case 1:


Input:
4 2
20 30 40 10
10
20

Output:
YES
YES

The array $A = [20, 30, 40, 10]$ is first sorted to become $[10, 20, 30, 40]$ .
For the first query, $X = 10$ , which is found in the sorted array, so the output is "YES".
For the second query, $X = 20$ , which is also found, so the output is "YES".

Test Case 2:


Input:
5 10
50 40 30 20 10
10
20
30
40
50
60
70
80
90
100

Output:
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO

The sorted array is $[10, 20, 30, 40, 50]$ .
The first five queries match elements in the array, so the outputs are "YES".
The remaining queries do not match any elements in the array, so the outputs are "NO".

This problem showcases efficient searching using sorting and binary search, leveraging time complexity improvements to handle large inputs effectively.

Scholar Career Network