Leetcode biweekly contest 96

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.

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

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

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 []int
func (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

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
}