New start day 7: 06/10/2020 Codechef October Long REPLESX

question (source:https://www.codechef.com/OCT20B/problems/REPLESX)

Replace for X

You are given an array of N integers and three more integers  and .

An operation on the array is defined to be: replace the -th smallest integer in the array with any integer you want.

Output the minimum number of operations you must perform on the array (possibly 0 operations) to make the -th smallest element of the array equal to . If it is impossible to do so output .

Note: the -th smallest number in an array is the -th number from the left when the array is sorted in non-decreasing order.

Input

  • The first line of the input contains a single integer T denoting the number of test cases. The description of test cases follows.
  • The first line of each test case contains four integers respectively.
  • The second line contains N space-separated integers 

Output

For each test case, print a single line containing one integer ― the minimum number of operations you must perform to make  the -th smallest element or  if its impossible to do so.

Constraints




  • The sum of N over all test cases does not exceed 
  •  for each valid i

Subtasks

Subtask #1 (10 points): 

Subtask #2 (40 points): The sum of  over all test cases does not exceed 

Subtask #3 (50 points): Original constraints

Example Input

2
5 4 3 4
4 9 7 0 8
2 25 1 2
100 20

Example Output

1
-1

Explanation

Example case 1:

  • We can perform one operation in the array. Take the -th smallest integer of the current array (which is  in this case) and replace it with . The array then becomes  which now makes  as the 3rd smallest number of the array.

Example case 2:

  • It is impossible to make  as the smallest number of the array.


MY logic:

This question is a logic-based question, doesn't involve any intense algorithm or data structure, except Sorting and binary search here and there.
First, let's try to find out the condition where it's not possible to make the value of p-th smallest number in the array equal to X.

for example:

array=[1,2,3,4,5,6,7,8,9]

p=2
k=3

let's analyze something. The array is already sorted so it's not a worry. Now we can change kth element and sort it every time. We will see that if we change the value of the kth element with anything higher then it goes to the right and if we change it to something smaller then it goes to the left.
1.- we cannot move a number n>arr[k-1] to the left of k no matter how much you tried. [updated to 3]
2- we cannot move a number n <arr[k+1] to the right of k no matter how many moves we took.[updated to 4]
3- if p<k then you cannot move a number n> arr[p] to p
4- if p>k then you cannot move any number n <arr[p] to p

so these are the condition which tell us the operation isn't possible.

Now for the ones which are possible we need to find the minimum number of moves.
 For the rest of the cases:
if p>k and x>arr[p]
 we search for lower-bound of x in the array and calculate the distance of p from it..similarly 
if p<k and x<arr[p] we search for upper bound of x in the array and calculate the distance of it from p.

My code:


 


Comments

Post a Comment

Popular posts from this blog

LeetCode 3Sum

Question Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Brute force We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:
Read more

30. Substring with Concatenation of All Words

Problem Statement You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order. Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. The substring starting at 0 is "barfoo". It is the concaten...
Read more

Lowest common ancestor in a binary Tree

Approach Define a recursive function rec that takes three parameters: root (the current node), p (first node to find the lowest common ancestor for), and q (second node to find the lowest common ancestor for). Check if the current node root is null or if it is either p or q . If any of these conditions is true, return the current node root as the lowest common ancestor. Recursively call the rec function for the left subtree of the current node and assign the result to a variable l . Recursively call the rec function for the right subtree of the current node and assign the result to a variable r . Check if both l and r are not null. If so, it means that p and q are found on different subtrees of the current node, and the current node root is their lowest common ancestor. Return the current node root . If l is null, it means that both p and q are on the right subtree (or not present in the tree). Return r . If none of the above conditions are met, it means ...
Read more