Given a unsorted sequence of positive integers and an integer M, return the first number in the sequence which is greater than M (or -1 if it doesn’t exist).
Example: if sequence = [2, 6, 50, 9, 1], M = 7 then ans = 50
O(log n) for each query required (after preprocessing).
My initial thought is using set or AVL trees but I am not getting the answer.
UPD: Let us suppose the array can’t be sorted as N is 10^7 and O(nlogn) sorting will not work
you can use hashing or sort the array using counting sort and apply binary search over the array or you can use treeset.
what if the array can’t be sorted. also I can use count sort because numbers can be big < 10^12. Let us suppose the array can’t be sorted as N is 10^7 and O(nlogn) sorting will not work
Are you sure \mathcal{O}(n \log n) will not work?
If you provide the problem source it will be helpful.
It’s quite simple…
My solution with O(N) preprocessing + O(logN) query
You just need a single observation to boil down this problem into a simple classical problem…
(if the array doesn’t change during the queries)
Here it goes…
Say, the given array is {5,4,3,8,9}
So, By trying various values of M, you can see, the output will never be 4 or 3, because a greater element (5) is already present to the left of both of these elements…
So, it doesn’t matter if you even store these elements.
You simply store the array {5, 8, 9}
Now i believe the binary search will get your answer…
However, if you need index of values rather than the actual values, you may go for mapping these values to their original indices…
If you still need help, refer to following code only after giving it an attempt
Hope that helps…
import java.util.*;
class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int N = in.nextInt();
ArrayList<Long> s = new ArrayList<>();
long c = in.nextLong();
s.add(c);
for(int i = 1; i < N; i++){
long x = in.nextLong();
if(x <= c)continue;
s.add(x);
c = x;
}
int Q = in.nextInt();
while(Q-->0){
long M = in.nextLong();
if(s.get(0) >= M)System.out.println(s.get(0));
else if(s.get(s.size()-1) < M)System.out.println(-1);
else System.out.println(search(s, M, 0, s.size()-1));
}
}
static long search(ArrayList<Long> s, long M, int l, int r){
int mid = (l+r)/2;
if(s.get(mid) >= M && (mid == 0 || s.get(mid-1) < M))return s.get(mid);
else if(s.get(mid) < M)return search(s, M, mid+1, r);
else return search(s,M, l,mid-1);
}
}
thanks a lot
yes i am sure
No problem 