Ninja and Sorted List

Moderate
0/80
3 upvotes
Asked in companies
MicrosoftLinkedInFacebook

Problem statement

There is a list of N files, and each file has a given file ID. Array ‘ARR’ contains the list of all file IDs.Ninja’s task is to tell whether a file with ID = ‘VAL’ exists in the list or not. So, to answer the query quickly, Ninja sorted the list. But, due to system error, the sorted array got rotated at an unknown pivot. Can you help Ninja with this problem?

You are given a rotated sorted array ‘ARR’ having ‘N’ elements and an integer ‘VAL’. You to check whether ‘VAL’ exists in the given array or not.

For Example 
If the ARR is [4,6,9,11,1,2,2] and ‘VAL’ is 4, the answer will be ‘YES’ as 4 exist in ‘ARR’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of elements in array ‘ARR’ and ‘VAL’ representing the number to be found.

The following line contains ‘N’ values corresponding to elements of ‘ARR’.
Output Format: 
For each test case, print ‘YES’ or ‘NO’ whether the ‘VAL’ exists in the array or not.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^7.
1 <=ARR[i] <=10^6.
1 <= VAL <= 10^6.

Time limit: 1 sec
Sample Input 1:
2
7 4
4 6 9 11 1 2 2
5 1
4 5 2 2 4
Sample Output 1:
YES
NO
Explanation of sample input 1:
For the first test case:
The answer is ‘YES’ as ‘VAL’ = 4 is present in the given array.

For the second test case:
The answer is ‘NO’ as ‘VAL’ = 1 is not present in the given array.
Sample Input 2:
2
8 6
9 9 9 10 2 3 6 6 
6 10
4 6 7 9 2 4
Sample Output 2:
YES
NO
Hint

Check the whole array.

Approaches (2)
Brute Force using Linear Search.

In this approach, we will simply perform a linear search over the array and try to find ‘VAL’. If we find ‘VAL’ , we will return True otherwise, return False.

 

Algorithm:

  • For i in range 0 to ‘N’ -1, do the following:
    • If ‘VAL’ is equal to ARR[i]:
      • ‘VAL’ is found.
      • Return True.
  • Return False.
Time Complexity

O(N), where ‘N’ is the number of elements in array ‘ARR’.

 

In this approach, we perform a linear search over the array, which takes N comparisons in the worst case. Hence, the overall time complexity is O(N).

Space Complexity

O(1).

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja and Sorted List
Full screen
Console