HackerRank‐Search - a920604a/leetcode GitHub Wiki

void whatFlavors(vector<int> cost, int money) {
    int n = cost.size();
    unordered_map<int,int> mp; //value map to index
    for(int i=0;i<n;++i) {
        if(mp.count(money - cost[i])){
            cout<<mp[money-cost[i] ] <<" "<<i+1<<endl;
            break;
        }
        mp[cost[i]] = i+1;
    }
}

int pairs(int k, vector<int> arr) {
    sort(arr.begin(), arr.end());
    // binary search
    int n = arr.size(), count = 0;
    for(int i=0;i<n-1;++i){
        int target = k+arr[i];
        int l = i+1, r = n-1;
        while(l<=r){
            int mid = l+ (r-l)/2;
            if(arr[mid]==target){
                count++;
                break;
            }
            else if(arr[mid] < target) l = mid+1;
            else r = mid-1;
        }
    }
    return count;
}

int pairs(int k, vector<int> arr) {
    unordered_map<int,int> mp;
    int count =0;
    for(int a:arr) mp[a]++;
    for(int a:arr){
        if(mp.count(a+k)) count+=mp[a+k];
    }
    return count;
}

vector<int> deDuplicate(vector<int> arr){
    vector<int> ret;
    // assume arr is sorted
    ret.push_back(arr[0]);
    for(int i=1; i<arr.size() ;++i){
        if(arr[i] == ret.back()) continue;
        ret.push_back(arr[i]);
    }
    return ret;
}
int FindTheMaxPos(vector<int> &nums, int target){
    int l =0, r = nums.size()-1;
    int ret = -1;
    while(l<=r){
        int mid = l+(r-l)/2;
        if(nums[mid] == target){
            ret = mid;
            l=mid+1;
        }
        else if(nums[mid] < target) l = mid+1;
        else r = mid-1;
    }
    return l;
}
// Complete the triplets function below.
long triplets(vector<int> a, vector<int> b, vector<int> c) {
    
    long count = 0;
    int lb=0;
    sort(a.begin(),a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    vector<int> arr = deDuplicate(a), brr = deDuplicate(b), crr = deDuplicate(c);
    while(lb<brr.size()){
       int ret = FindTheMaxPos(arr, brr[lb]);
       int ret2 = FindTheMaxPos(crr, brr[lb]);
       count+=(long)ret*ret2;
       lb++;  
    }
    return count;

}

long calMinTime(vector<long> machines, long times){
    long ret = 0;
    for(long n:machines){
        ret+=(times/n);
    }
    return ret;
}
// Complete the minTime function below.
long minTime(vector<long> machines, long goal) {
    long l = 0, r= 0;
    for(long a:machines) r = max(r, a);
    r*=goal;
    while(l<r){
        long mid = l + (r-l)/2;
        long val = calMinTime(machines, mid);
        // cout<<l<<" "<<r<<"\t spend time: "<<mid<<"\tcost: "<<val<<" "<<goal<<endl;
        if(val == goal) r=mid;
        else if(val > goal) r = mid;
        else l = mid+1;
    }
    return l;
}

void traverse(vector<long> &a, vector<int> & path , int start, long &ret, long m){
    long sum = 0;
    for(long t:path){
        sum+=t;
        // cout<<t<<" ";
    }
    // cout<<endl;
    ret = max(ret, sum%m);
    
    if(start == a.size()) return;
   
    path.push_back(a[start]);
    traverse(a, path, start+1, ret, m);
    path.pop_back();
    
    
    
}
long maximumSum(vector<long> a, long m) {
    long ret = 0;
    int n = a.size();
    // sub array
    //  3   3   2   2   5
    vector<int> path;
    for(int i=0;i<a.size() ;++i)
        traverse(a, path, i, ret, m);
    return ret;
}

long getPosition(vector<long> & nums, long target){
    //  3, insert 6 => 1
    //  3   6 insert 1 => 0
    //  1   3   6 insert 3 => 1
    //  1   3   3   6 insert 1=> 0
    
    //  1   insert 5 => 1
    //  1   5 insert 9 => 2
    // if(nums.empty()) return 0;
    int  l=0, r= nums.size();
    while (l<r) {
        int mid = l + (r-l)/2;
        if(nums[mid] >= target) r=mid;
        else if(nums[mid] < target) l = mid + 1;
    }
    return l;
}
long maximumSum(vector<long> a, long m) {
    //  7
    //  3   3   2   2   5
    //c 3   6   1   3   1
    //p 0   1   0   1   0
    //d 0   0   3   3   1
    //r 3   
    //  3   6
    //  1   3   6
    //  1   3   3   6
    //  1   1   3   3   6
    
    long cur = 0, ret=0;
    vector<long> vec;
    for(int i=0;i<a.size() ; ++i){
        cur = (cur+a[i]) %m;
        long pos = getPosition(vec, cur);
        long d = pos == vec.size() ? 0 : vec[pos];
        vec.insert(vec.begin()+pos,cur);
        ret = max(ret, (cur+m-d)%m);
    }
    return ret;
}