DSA-java/lc888.java at main · yashwan7/DSA-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.HashSet;

public class lc888 {
class Solution {
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
       int sumA = 0;
        int sumB = 0;
        for (int a : aliceSizes) {
            sumA += a;
        }
        for (int b : bobSizes) {
            sumB += b;
        }
//After swapping a and b,
//sumA - a + b = sumB - b + a
int diff = (sumA - sumB) / 2;

        HashSet<Integer> set = new HashSet<>();

        for (int a : aliceSizes) {
            set.add(a);
        }
        for (int b : bobSizes) {
            int required = b + diff;

            if (set.contains(required)) {
                return new int[]{required, b};
            }
        }

        return new int[]{};
    }
}
//Time Complexity
//Calculating sums: O(n + m)
//Building HashSet: O(n)
//Searching: O(m)
//Overall: O(n + m)

//class Solution {
 //   public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
//
 //       int sumA = 0;
 //       int sumB = 0;
//
 ///       for (int a : aliceSizes) sumA += a;
 //       for (int b : bobSizes) sumB += b;
//
 //       int diff = (sumA - sumB) / 2;
//
 ////       Arrays.sort(aliceSizes);
//
 //       for (int b : bobSizes) {
//
 //           int target = b + diff;
//
 //           int start = 0;
 //           int end = aliceSizes.length - 1;
//
  //          while (start <= end) {
//
  //              int mid = start + (end - start) / 2;
//
  //              if (aliceSizes[mid] == target) {
  //                  return new int[]{target, b};
  //              } else if (aliceSizes[mid] < target) {
  //                  start = mid + 1;
  //              } else {
  //                  end = mid - 1;
  //              }
  //          }
  //      }

  //      return new int[]{};

  //  }
//}
}