# Leetcode biweekly contest 96

January 23, 2023

## Minimum Common Value (opens in a new tab)

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.

func getCommon(nums1, nums2 []int) int { m := make(map[int]bool) for _, n := range nums2 { m[n] = true } for _, n := range nums1 { if m[n] { return n } } return -1}

## Minimum Operations to Make Array Equal II (opens in a new tab)

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.

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

## Maximum Subsequence Score (opens in a new tab)

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.

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

## Check if Point Is Reachable (opens in a new tab)

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)

func isReachable(targetX int, targetY int) bool { tx, ty := targetX, targetY for tx&1 == 0 { tx >>= 1 } for ty&1 == 0 { ty >>= 1 } g := gcd(tx, ty) if g == 1 { return true } return false}func gcd(a, b int) int { for b != 0 { a, b = b, a%b } return a}