Minimum Loss

help
1

Problem Link:

Log In | HackerEarth

Basically in this problem we are given an array
We have to find minimum A[i]-A[j]
Such that i>j and A[i]>A[j]

Pls help in this problem…
@anon55659401
@nuttela
@s5960r

I am using upper bound in sets but still wrong answer

2

Use some precomputation :wink:

Now think along it… I’ll tell you the full method in 10 mins if u are unable to figure out

3

Basically do binary search each time.

  1. When you traverse along the array and if you are at an current index i, then all the previous indices (1 -> i-1) are j’s indices. They are sorted [I will tell how as you go through below steps].
  2. Now take this i’th index value and insert it in a proper position using Binary search technique because 1 -> i-1 are sorted. Also, during binary search find the immediate smallest element that is smaller than the current i’th element.
    a) Now the [element which was in ith position] - [It’s immediate previous element after binary search insertion] will be minimum for this i’th element.
  1. Now as you see, based on step, 2 you have inserted the ith index element in a sorted position [That’s why I told 1 -> i - 1 will always be sorted].
  1. Repeat process 1 -> 3 and find the minimum difference.

Hope it helps. :slight_smile:

4

it takes O(n) time to insert element in between of vector or array.

5

O(log n) to use binary search
and use linked list to insert in between two elements in O(1).

6

binary search on linked list is never a good choice. your same logic with set is nice option.

7

Set neither “maintains order” nor holds “duplicates” unless you do some crazy things like using LinkedHashSet (or) Hacky-Comparator to allow duplicates [Still not better as you need to use TreeSet in that case]. Too much of desicion makings and no proper way of using them.

Linked list seems best here, afaik. DataStructures are fine. It is always a comparable desicions to use. Since inserting in the middle takes O(1) operation, I suggested LinkedList. Incase using Vector/ArrayList makes the insertion [elsewhere] O(n) in worstcase. Set, no way!

8

i want you to solve this question using linkedlist and multiorderset both , you will get to know a difference.

1 Like
9

Ohh! will try that :slight_smile:

10

code

Here’s the code using lower_bound and set from C++ STL.

It’s passing all test cases except 1, It’s giving TLE :frowning_face:

Might be some corner case I’m missing. Try and debug someone. I’ll do it later

2 Likes
11

i have solve it 90% one test case cross time limit
if you want i share you the logic

12

is this can be solved using bit and hashing like in case of inversion counting??

13

your code is failing on 2 test cases

1 wrong answer and 1 TLE

14

Now your code give wrong answer at one input.
By changing one line TLE is removed…
Instead of using lower_bound(s.begin(),s.end(),num[i])
USE
s.lower_bound(num[i])…
for explanation refer Difference in these two ways of using lower_bound [C++] - Codeforces
I hope it will help

15

thanks !! are you able to figure out corner case

16

Yes…
Link-Online Compiler and IDE - GeeksforGeeks

17

Seems a really easy question. Just use upper_bound on set.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, loss = INT_MAX;
    cin >> n;
    set<long long> st;
    
    for(int i = 0; i < n; ++i) {
        long long num;
        cin >> num;
        
        if(st.find(num) != st.end())
            loss = 0;
        
        else {
            auto ub = st.upper_bound(num);
            if(ub != st.end())
                loss = min(loss, *ub - num);
        }
        
        st.insert(num);
    }
    
    cout << loss << endl;
}
18

//You can check this successful solution done in C.

#include<stdio.h>
#include<stdlib.h>
void merge(long long* arr, int low,int mid,int high){
long long L[mid-low+2];
long long R[high-mid+1];
for(long i=0;i<mid-low+1;i++){
L[i]=arr[low+i];
}
for(long i=0;i<high-mid;i++){
R[i]=arr[mid+i+1];
}
L[mid-low+1]=100000000000000000;
R[high-mid]=100000000000000000;
long count1=0;
long count2=0;
for(long i=low;i<high+1;i++){
if(L[count1]<R[count2]){
arr[i]=L[count1];
count1++;
}else{
arr[i]=R[count2];
count2++;
}
}
}
void mergesort(long long* arr,int low,int high){
if(low==high){
return;
}else{
int mid=(low+high)/2;
mergesort(arr,low,mid);
mergesort(arr,mid+1,high);
merge(arr,low,mid,high);
}}
int search(long long* arr,long long a,int length){
for(int i=0;i<length;i++){
if(arr[i]==a){
return i;
}
}
}
int main(){
int length;
scanf("%d",&length);
long long* arr=(long long*)malloc(lengthsizeof(long long));
long long array=(long long*)malloc(length*sizeof(long long));
for(int i=0;i<length;i++){
scanf("%lld",&arr[i]);
}
for(int i=0;i<length;i++){
array[i]=arr[i];
}
mergesort(arr,0,length-1);
long long min=100000000000000000;
for(int i=length-1;i>0;i–){
if(arr[i]-arr[i-1]<min){
if(search(array,arr[i],length)<search(array,arr[i-1],length)){
min=arr[i]-arr[i-1];
}
}
}
printf("%lld",min);
free(arr);
free(array);
return 0;
}