Published on

# Leetcode biweekly contest 96

Authors
• Name
Moch Lutfi
@kaptenupi

## Minimum Common Value

The function `getCommon` takes two slices of integers, `nums1` and `nums2`, as input and returns the first common element between the two slices. The function first creates an empty map `m` of type `map[int]bool`. It then iterates through each element in `nums2` and adds them to the map with the value `true`. This is done so that we can quickly check if an element in `nums1` also exists in `nums2` later on.

Next, the function iterates through each element in `nums1`. For each element, it checks if the element exists in the map `m` by checking the value of `m[n]`. If the element exists in the map, the function returns the element as it is the first common element between the two slices. If no common element is found, the function returns -1. This implementation uses a hashmap to check if the element exists or not which makes the time complexity O(n) which is faster than iterating through the slices.

`_12func getCommon(nums1, nums2 []int) int {_12 m := make(map[int]bool)_12 for _, n := range nums2 {_12 m[n] = true_12 }_12 for _, n := range nums1 {_12 if m[n] {_12 return n_12 }_12 }_12 return -1_12}`

## Minimum Operations to Make Array Equal II

The algorithm concept behind this code is to find the minimum number of operations needed to change the elements in `nums1` to the elements in `nums2` such that the difference between each element is a multiple of `k`.

The code first checks if `k` is equal to 0. If it is, the function checks if the elements in `nums1` are the same as the elements in `nums2`. If they are, it returns 0, otherwise it returns -1. If `k` is not 0, the function iterates through the elements in `nums1` and `nums2`. For each pair of elements, it calculates the absolute difference and checks if the difference is divisible by `k`. If it is not divisible, the function returns -1. If it is divisible, it increments the count of positive or negative operations needed.

After iterating through all pairs of elements, the function checks if the number of positive and negative operations needed are equal. If they are not, it returns -1, otherwise it returns the number of positive operations needed.

`_27func minOperations(nums1, nums2 []int, k int) int64 {_27 var ne, po int64_27 if k == 0 {_27 for i := 0; i < len(nums1); i++ {_27 if nums1[i] != nums2[i] {_27 return -1_27 }_27 }_27 return 0_27 }_27 for i := 0; i < len(nums1); i++ {_27 a, b := nums1[i], nums2[i]_27 u := int64(math.Abs(float64(a - b)))_27 if u % int64(k) != 0 {_27 return -1_27 }_27 if a > b {_27 ne += u / int64(k)_27 } else {_27 po += u / int64(k)_27 }_27 }_27 if ne != po {_27 return -1_27 }_27 return po_27}`

## Maximum Subsequence Score

The algorithm concept behind this code is to find the maximum score that can be obtained by selecting elements from both slices `nums1` and `nums2` such that the total number of selected elements is exactly `k`.

The code first creates a 2D array `a` of size `n` where `n` is the length of the input slices. It then populates this array with the elements from `nums1` and `nums2` in the form of pairs. The array is then sorted based on the first element of each pair in ascending order and if the first element is the same, sort based on the second element in ascending order.

Then, the code creates a min heap `pq` of type `IntHeap`. It also initializes a variable `ans` and `s` to keep track of the maximum score and the total score respectively. Then, the code iterates through the pairs in the array starting from the last element. For each pair, it pushes the second element of the pair into the heap and adds it to the total score. If the heap's length is greater than k, the code pops the smallest element from the heap and subtracts it from the total score. If the heap's length is equal to k, it compares the total score with the maximum score and update the maximum score if the total score is greater. Finally, the function returns the maximum score.

`_60import (_60 "container/heap"_60 "fmt"_60)_60_60type IntHeap []int_60_60func (h IntHeap) Len() int { return len(h) }_60func (h IntHeap) Less(i, j int) bool {_60 return h[i] < h[j]_60}_60func (h IntHeap) Swap(i, j int) {_60 h[i], h[j] = h[j], h[i]_60}_60func (h *IntHeap) Push(x interface{}) {_60 *h = append(*h, x.(int))_60}_60func (h *IntHeap) Pop() interface{} {_60 n := len(*h)_60 x := (*h)[n-1]_60 *h = (*h)[:n-1]_60 return x_60}_60_60func maxScore(nums1, nums2 []int, k int) int64 {_60 n := len(nums1)_60 a := make([][]int, n)_60 for i := 0; i < n; i++ {_60 a[i] = []int{nums2[i], nums1[i]}_60 }_60 sort.Slice(a, func(i, j int) bool {_60 if a[i] != a[j] {_60 return a[i] < a[j]_60 }_60 return a[i] < a[j]_60 })_60 pq := &IntHeap{}_60 heap.Init(pq)_60 var ans, s int64_60 for i:=n-1; i >= 0;i--{_60 heap.Push(pq, a[i])_60 s += int64(a[i])_60 if(pq.Len() > k){_60 s -= int64(heap.Pop(pq).(int))_60 }_60 if(pq.Len() == k){_60 ans = max(ans, s * int64(a[i]))_60 }_60 }_60 return ans_60}_60 _60_60func max(a, b int64)int64{_60 if a < b{_60 return b_60 }_60 _60 return a_60}`

## Check if Point Is Reachable

The algorithm concept behind this code is to check if a point (targetX, targetY) is reachable from the origin (0,0) by taking steps of size (1,0) and (0,1) only.

The function `isReachable` takes two integers, `targetX` and `targetY` as input and returns a boolean value indicating whether the point is reachable or not. The function first assigns the input values to two variables `tx` and `ty`. It then iterates through both variables using a for loop and bitwise operator `&` and shift operator `>>=`. It repeatedly divides the variable by 2 using the shift operator until the variable becomes an odd number. This is done to check if the targetX and targetY are reachable or not.

The function then calls another function `gcd` which takes two integers as input and returns the greatest common divisor of the two integers using the Euclidean algorithm. The Euclidean algorithm repeatedly applies the modulo operator `%` and the assignment operator `=` to find the greatest common divisor of two integers.

Then the function checks if the gcd of tx and ty is 1 or not. If it is 1, it means that the point is reachable and the function returns true, otherwise it returns false. The idea behind this is that if gcd of targetX and targetY is 1, it means that both targetX and targetY can be represented as a linear combination of 1 and 0 using the Euclidean algorithm. In other words, the point is reachable and this is based on the Bézout's identity theorem which states that for any two integers a and b, there exist integers x and y such that ax + by = gcd(a, b)

`_21func isReachable(targetX int, targetY int) bool {_21 tx, ty := targetX, targetY_21 for tx&1 == 0 {_21 tx >>= 1_21 }_21 for ty&1 == 0 {_21 ty >>= 1_21 }_21 g := gcd(tx, ty)_21 if g == 1 {_21 return true_21 }_21 return false_21}_21_21func gcd(a, b int) int {_21 for b != 0 {_21 a, b = b, a%b_21 }_21 return a_21}`