Advertisement
CR7CR7

BuyTwoItems

May 25th, 2023
1,159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.37 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. class Solution {
  4.     public int solve(List<Integer> price, int a, int b) {
  5.         Collections.sort(price);
  6.         int count = 0;
  7.         int n = price.size();
  8.        
  9.         for (int i = 0; i < n; i++) {
  10.             int target1 = a - price.get(i);
  11.             int target2 = b - price.get(i);
  12.            
  13.             int left = i + 1;
  14.             int right = n - 1;
  15.            
  16.             int lowerBound = lowerBound(price, left, right, target1);
  17.             int upperBound = upperBound(price, left, right, target2);
  18.            
  19.             count += upperBound - lowerBound + 1;
  20.         }
  21.        
  22.         return count;
  23.     }
  24.    
  25.     private int lowerBound(List<Integer> price, int left, int right, int target) {
  26.         while (left <= right) {
  27.             int mid = left + (right - left) / 2;
  28.             if (price.get(mid) >= target) {
  29.                 right = mid - 1;
  30.             } else {
  31.                 left = mid + 1;
  32.             }
  33.         }
  34.         return left;
  35.     }
  36.    
  37.     private int upperBound(List<Integer> price, int left, int right, int target) {
  38.         while (left <= right) {
  39.             int mid = left + (right - left) / 2;
  40.             if (price.get(mid) > target) {
  41.                 right = mid - 1;
  42.             } else {
  43.                 left = mid + 1;
  44.             }
  45.         }
  46.         return right;
  47.     }
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement