Refine 1981 and 1539 format and link

qiyuangong · qiyuangong · commit 687fa4ca7234 · 2021-12-05T20:53:42.000+08:00
diff --git a/README.md b/README.md
@@ -236,6 +236,8 @@ I'm currently working on [Analytics-Zoo](https://github.com/intel-analytics/anal
 | 1342 | [Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/1342_Number_of_Steps_to_Reduce_a_Number_to_Zero.py) | If number is divisible by 2, divide the number by 2, else subtract 1 from the number, and output the number of steps, O(logn) and O(1) |
 | 1365 | [How Many Numbers Are Smaller Than the Current Number](https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/1365_How_Many_Numbers_Are_Smaller_Than_the_Current_Number.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1365_How_Many_Numbers_Are_Smaller_Than_the_Current_Number.java) | 1. Sort and get position in sorted nums, O(nlogn) and O(n)<br>2. Fill count into 0-100, O(n) and O(1) |
 | 1480 | [Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/1480_Running_Sum_of_1d_Array.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1480_Running_Sum_of_1d_Array.java) | 1. Go through the array, O(n) and O(1)<br>2. Accumulate API |
+| 1539 | [Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/) | [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1539_Kth_Missing_Positive_Number.java) | Binary search, num of missing = arr[i]-i-1 |
+| 1981 | [Minimize the Difference Between Target and Chosen Elements](https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/) | [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1981_Minimize_the_Difference_Between_Target_and_Chosen_Elements.java) | DP memo[row][sum] to avoid recomputing |
 
 | # | To Understand |
 |---| ----- |
diff --git a/java/1533_Kth_Missing_Positive_Number.java b/java/1533_Kth_Missing_Positive_Number.java
diff --git a/java/1539_Kth_Missing_Positive_Number.java b/java/1539_Kth_Missing_Positive_Number.java
@@ -0,0 +1,43 @@
+class Solution {
+    public int findKthPositive(int[] a, int k) {
+        int B[] = new int[a.length];
+
+        // equation (A)
+        // B[i]=a[i]-i-1
+        // B[i]=number of missing numbers BEFORE a[i]
+        for (int i = 0; i < a.length; i++)
+            B[i] = a[i] - i - 1; // -1 is done as here missing numbers start from 1 and not 0
+
+        // binary search upper bound of k
+        // smallest value>=k
+
+        int lo = 0, hi = B.length - 1;
+
+        while (lo <= hi) {
+            int mid = lo + (hi - lo) / 2;
+
+            if (B[mid] >= k)
+                hi = mid - 1;
+            else
+                lo = mid + 1;
+        }
+
+        // lo is the answer
+
+        /*
+         * now the number to return is a[lo]-(B[lo]-k+1) (EQUATION B)
+         * where (B[lo]-k+1) is the number of steps we need to go back
+         * from lo to retrieve kth missing number, since we need to find
+         * the kth missing number BEFORE a[lo], we do +1 here as
+         * a[lo] is not a missing number when B[lo]==k
+         * putting lo in equation(A) above
+         * B[i]=a[i]-i-1
+         * B[lo]=a[lo]-lo-1
+         * and using this value of B[lo] in equation B
+         * we return a[lo]-(a[lo]-lo-1-k+1)
+         * we get lo+k as ans
+         * so return it
+         */
+        return lo + k;
+    }
+}
diff --git a/java/1981_Minimize_the_Difference_Between_Target_and_Chosen_Elements.java b/java/1981_Minimize_the_Difference_Between_Target_and_Chosen_Elements.java
@@ -1,28 +1,29 @@
 class Solution {
     public int minimizeTheDifference(int[][] a, int k) {
-        n=a.length;
-        m=a[0].length;        
-        min=Integer.MAX_VALUE;
-        dp=new boolean[n][5000];
-        solve(a,k,0,0,0);
+        n = a.length;
+        m = a[0].length;
+        min = Integer.MAX_VALUE;
+        dp = new boolean[n][5000];
+        solve(a, k, 0, 0, 0);
         return min;
     }
-    private void solve(int a[][],int k,int sum,int row,int col)
-    {
-        if(dp[row][sum]) return;
-        if(n-1==row)
-        {
-            for(int i=0;i<m;i++)
-            min=Math.min(min,Math.abs(k-sum-a[row][i]));
-            dp[row][sum]=true;
+
+    private void solve(int a[][], int k, int sum, int row, int col) {
+        if (dp[row][sum])
+            return;
+        if (n - 1 == row) {
+            for (int i = 0; i < m; i++)
+                min = Math.min(min, Math.abs(k - sum - a[row][i]));
+            dp[row][sum] = true;
             return;
         }
-        
-        for(int i=0;i<m;i++)
-            solve(a,k,sum+a[row][i],row+1,col);
-        dp[row][sum]=true;
+
+        for (int i = 0; i < m; i++)
+            solve(a, k, sum + a[row][i], row + 1, col);
+        dp[row][sum] = true;
     }
+
     private int min;
-    private int dy[],n,m;
+    private int dy[], n, m;
     private boolean dp[][];
 }
