Published on

Leetcode biweekly contest 96

Authors

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.


_12
func 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.


_27
func 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.


_60
import (
_60
"container/heap"
_60
"fmt"
_60
)
_60
_60
type IntHeap []int
_60
_60
func (h IntHeap) Len() int { return len(h) }
_60
func (h IntHeap) Less(i, j int) bool {
_60
return h[i] < h[j]
_60
}
_60
func (h IntHeap) Swap(i, j int) {
_60
h[i], h[j] = h[j], h[i]
_60
}
_60
func (h *IntHeap) Push(x interface{}) {
_60
*h = append(*h, x.(int))
_60
}
_60
func (h *IntHeap) Pop() interface{} {
_60
n := len(*h)
_60
x := (*h)[n-1]
_60
*h = (*h)[:n-1]
_60
return x
_60
}
_60
_60
func 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][0] != a[j][0] {
_60
return a[i][0] < a[j][0]
_60
}
_60
return a[i][1] < a[j][1]
_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][1])
_60
s += int64(a[i][1])
_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][0]))
_60
}
_60
}
_60
return ans
_60
}
_60
_60
_60
func 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)


_21
func 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
_21
func gcd(a, b int) int {
_21
for b != 0 {
_21
a, b = b, a%b
_21
}
_21
return a
_21
}