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.
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);
}
}
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.
thanks a lot
yes i am sure
No problem 
thanks.
Using Segment Tree with Binary search it can be solved in O(log(n) * log(n))
Create a prefix array which stores max element upto index i and print the lower bound of M in the prefix array as answer. If index is required then just store a pair in the prefix array. Note:- It works only if there is no update and if there is update use segment tree.
Can you please describe the algorithm in details.
make new array arr of the same size and the element arr[i] is the max value of the numbers from 0 to i in the original array now lower bound on it with your value
Thanks a lot bro
can you implement the sort function then call into the search function then it willl works
#include<stdio.h>
void sorted(int arr,int n){
int i,j;
for( i=0;i<n;i++ ){
for( j=i+1;j<n;j++){
if(arr[i]>arr[j]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
int binaryserach(int arr,int n,int lb,int ub,int target){
sorted(arr,n);
while(lb<=ub){
int mid=lb+(ub-lb)/2;
if(arr[mid]==target){
return mid;
}
elseif(arr[mid]>target)
{
binaryserach(arr,n,lb,ub+1,target);
}
else{
binaryserach(arr,n,lb+1,ub,target);
}
}
return -1;
}
void main(){
int n;
scanf(“%d”,&n);
int target;
scanf(“%d”,&target);
int arr[100];
for(int i=0;i<n;i++){
scanf(“%d”,&arr[i]);
}
int r=binaryserach(arr,n,0,n-1,target);
if(r!= -1){
printf(“%d”,r);
}
else{
printf(“%d”,r= -1);
}
}
