Weekly Contest 280 LeetCode Solution

Problem 1 – Count Operations to Obtain Zero Leetcode Solution

You are given two non-negative integers num1 and num2.

In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.

  • For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

Constraints:

  • 0 <= num1, num2 <= 105

Count Operations to Obtain Zero Leetcode Solution in Java

    public int countOperations(int num1, int num2) {
        int cnt = 0;
        while (Math.min(num1, num2) > 0) {
            if (num1 < num2) {
                int tmp = num1;
                num1 = num2;
                num2 = tmp;
            }
            cnt += num1 / num2;
            num1 %= num2;
        }
        return cnt;
    }

Count Operations to Obtain Zero Leetcode Solution in Python 3

    def countOperations(self, num1: int, num2: int) -> int:
        cnt = 0
        while min(num1, num2) > 0:
            if num1 < num2:
                num1, num2 = num2, num1
            ops, num1 = divmod(num1, num2)    
            cnt += ops
        return cnt

Count Operations to Obtain Zero Leetcode Solution in C++

int countOperations(int a, int b) {
    int res = 0;
    while (min(a, b) > 0) {
        if (a > b)
            swap(a, b);
        res += b / a;
        b %= a;
    }
    return res;
}

Count Operations to Obtain Zero Leetcode Solution in Python

def countOperations(self, num1: int, num2: int) -> int:
	operations = 0

	while num1 and num2:
		if num2 > num1:
			num2 -= num1
			operations += 1

		if num1 > num2:
			num1 -= num2
			operations += 1

		if num1 == num2:
			return operations + 1

	return operations

Count Operations to Obtain Zero Leetcode Solution in JavaScript

var countOperations = function (num1, num2) {
    if (num2 === 0) return 0;                       // done
    if (num1 < num2) countOperations(num2, num1);   // reverse if num1 is small
    return (
        Math.trunc(num1 / num2) +                   // quotient (equals repeated subtraction amount)
        countOperations(num2, num1 % num2)          // call smaller, remainder
    );
};

Problem 2 – Minimum Operations to Make the Array Alternating Leetcode Solution

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

  • nums[i - 2] == nums[i], where 2 <= i <= n - 1.
  • nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations. 

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Minimum Operations to Make the Array Alternating Leetcode Solution in C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        
        int totalEven = 0, totalOdd = 0;
        
        unordered_map<int,int> mapEven, mapOdd;
        
        for(int i=0;i<nums.size();i++) {
            if(i%2==0) {
                totalEven++;
                mapEven[nums[i]]++;
            }
            
            else {
                totalOdd++;
                mapOdd[nums[i]]++;
            }
        }
        
        
        int firstEvenCount = 0, firstEven = 0;
        int secondEvenCount = 0, secondEven = 0;
        
        for(auto it=mapEven.begin();it!=mapEven.end();it++) {
            int num = it->first;
            int count = it->second;
            
            if(count>=firstEvenCount) {
                secondEvenCount = firstEvenCount;
                secondEven = firstEven;
                firstEvenCount = count;
                firstEven = num;
            }
            
            else if(count >= secondEvenCount) {
                secondEvenCount = count;
                secondEven = num;
            }
        }
        
        
        int firstOddCount = 0, firstOdd = 0;
        int secondOddCount = 0, secondOdd = 0;
        
        
        for(auto it=mapOdd.begin();it!=mapOdd.end();it++) {
            int num = it->first;
            int count = it->second;
            
            if(count>=firstOddCount) {
                secondOddCount = firstOddCount;
                secondOdd = firstOdd;
                firstOddCount = count;
                firstOdd = num;
            }
            
            else if(count>=secondOddCount) {
                secondOddCount = count;
                secondOdd = num;
            }
        }
        
        int operationsEven = 0, operationsOdd = 0;
        
        
        operationsEven = totalEven - firstEvenCount;
        
        if(firstEven!=firstOdd) operationsEven += (totalOdd - firstOddCount);
        else operationsEven += (totalOdd - secondOddCount);
        
        
        operationsOdd = totalOdd - firstOddCount;
        if(firstOdd!=firstEven) operationsOdd += (totalEven - firstEvenCount);
        else operationsOdd += (totalEven - secondEvenCount);
        
        
        return min(operationsEven, operationsOdd);
        
    }
};

Minimum Operations to Make the Array Alternating Leetcode Solution in Java

class Solution {
    public int minimumOperations(int[] nums) {
        int freq[][] = new int[100005][2];
        int i, j, k, ans=0;
        for(i = 0; i < nums.length; i++) {
    			freq[nums[i]][i&1]++;
    		}
    		
    		for(i = 1, j=k=0; i <= 100000; i++) {
			// Add the maximum frequency of odd indexes to maximum frequency even indexes 
		    //and vice versa, it will give us how many elements we don't need to change. 
    		ans = Math.max(ans, Math.max(freq[i][0] + k, freq[i][1] + j));
            j = Math.max(j, freq[i][0]);
            k = Math.max(k, freq[i][1]);
        }
        return nums.length - ans;
    }
}

Minimum Operations to Make the Array Alternating Leetcode Solution in Python 3

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        odd, even = defaultdict(int), defaultdict(int)
        for i in range(n):
            if i % 2 == 0:
                even[nums[i]] += 1
            else:
                odd[nums[i]] += 1
        topEven, secondEven = (None, 0), (None, 0)
        for num in even:
            if even[num] > topEven[1]:
                topEven, secondEven = (num, even[num]), topEven
            elif even[num] > secondEven[1]:
                secondEven = (num, even[num])
        topOdd, secondOdd = (None, 0), (None, 0)
        for num in odd:
            if odd[num] > topOdd[1]:
                topOdd, secondOdd = (num, odd[num]), topOdd
            elif odd[num] > secondOdd[1]:
                secondOdd = (num, odd[num])
        if topOdd[0] != topEven[0]:
            return n - topOdd[1] - topEven[1]
        else:
            return n - max(secondOdd[1] + topEven[1], secondEven[1] + topOdd[1])

Minimum Operations to Make the Array Alternating Leetcode Solution in

		odd=defaultdict(int) #frequency table to count frequency of odd elements in array 
        even=defaultdict(int) #frequency table to count frequency of even elements in array 
        for i in range(len(nums)):
            if i%2:
                even[nums[i]]+=1
            else:
                odd[nums[i]]+=1
        even[-1]=0      #just in case there is only one element in even to avoid index out of range in last line of code 
        odd[-2]=0
        a=sorted([(odd[i],i) for i in odd],reverse=True)
        b=sorted([(even[i],i) for i in even],reverse=True)#sorting to get element with max freq a[0][0] represents element with most frequency and a[0][1] is the element
        if a[0][1]!=b[0][1]:    #according to given condition even and odd should be different 
            return len(nums)-a[0][0]-b[0][0]    
        return len(nums)-max(a[0][0]+b[1][0],a[1][0]+b[0][0])# else taking second element with max freq from odd and even to calculate min  
            

Problem 3 – Removing Minimum Number of Magic Beans Leetcode Solution

You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag.

Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal. Once a bean has been removed from a bag, you are not allowed to return it to any of the bags.

Return the minimum number of magic beans that you have to remove.

Example 1:

Input: beans = [4,1,6,5]
Output: 4
Explanation: 
- We remove 1 bean from the bag with only 1 bean.
  This results in the remaining bags: [4,0,6,5]
- Then we remove 2 beans from the bag with 6 beans.
  This results in the remaining bags: [4,0,4,5]
- Then we remove 1 bean from the bag with 5 beans.
  This results in the remaining bags: [4,0,4,4]
We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that remove 4 beans or fewer.

Example 2:

Input: beans = [2,10,3,2]
Output: 7
Explanation:
- We remove 2 beans from one of the bags with 2 beans.
  This results in the remaining bags: [0,10,3,2]
- Then we remove 2 beans from the other bag with 2 beans.
  This results in the remaining bags: [0,10,3,0]
- Then we remove 3 beans from the bag with 3 beans. 
  This results in the remaining bags: [0,10,0,0]
We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that removes 7 beans or fewer.

Constraints:

  • 1 <= beans.length <= 105
  • 1 <= beans[i] <= 105

Removing Minimum Number of Magic Beans Leetcode Solution in C++

class Solution {
public:
    long long minimumRemoval(vector<int>& A) {
        long N = A.size(), ans = LLONG_MAX, sum = accumulate(begin(A), end(A), 0L);
        sort(begin(A), end(A));
        for (int i = 0; i < N; ++i) ans = min(ans, sum - (N - i) * A[i]);
        return ans;
    }
};

Removing Minimum Number of Magic Beans Leetcode Solution in Java

class Solution {
    public long minimumRemoval(int[] A) {
        long N = A.length, ans = Long.MAX_VALUE, sum = 0;
        for (int n : A) sum += n;
        Arrays.sort(A);
        for (int i = 0; i < N; ++i) ans = Math.min(ans, sum - (N - i) * A[i]);
        return ans;
    }
}

Removing Minimum Number of Magic Beans Leetcode Solution in Python 3

class Solution:
    def minimumRemoval(self, A: List[int]) -> int:
        return sum(A) - max((len(A) - i) * n for i, n in enumerate(sorted(A)))

Removing Minimum Number of Magic Beans Leetcode Solution in Python

def minimumRemoval(self, beans: List[int]) -> int:
	beans.sort()
	s = sum(beans)
	l = len(beans)
	res = float('inf')

	for i in range(len(beans)):
		res = min(res, s - l * beans[i])
		l -= 1
		
	return res

Problem 4 – Maximum AND Sum of Array Leetcode Solution

You are given an integer array nums of length n and an integer numSlots such that 2 * numSlots >= n. There are numSlots slots numbered from 1 to numSlots.

You have to place all n integers into the slots such that each slot contains at most two numbers. The AND sum of a given placement is the sum of the bitwise AND of every number with its respective slot number.

  • For example, the AND sum of placing the numbers [1, 3] into slot 1 and [4, 6] into slot 2 is equal to (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4.

Return the maximum possible AND sum of nums given numSlots slots.

Example 1:

Input: nums = [1,2,3,4,5,6], numSlots = 3
Output: 9
Explanation: One possible placement is [1, 4] into slot 1, [2, 6] into slot 2, and [3, 5] into slot 3. 
This gives the maximum AND sum of (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9.

Example 2:

Input: nums = [1,3,10,4,7,1], numSlots = 9
Output: 24
Explanation: One possible placement is [1, 1] into slot 1, [3] into slot 3, [4] into slot 4, [7] into slot 7, and [10] into slot 9.
This gives the maximum AND sum of (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24.
Note that slots 2, 5, 6, and 8 are empty which is permitted.

Constraints:

  • n == nums.length
  • 1 <= numSlots <= 9
  • 1 <= n <= 2 * numSlots
  • 1 <= nums[i] <= 15

Maximum AND Sum of Array Leetcode Solution in Java

    public int maximumANDSum(int[] A, int ns) {
        int mask = (int)Math.pow(3, ns) - 1;
        int[] memo = new int[mask + 1];
        return dp(A.length - 1, mask, ns, memo, A);
    }
    
    private int dp(int i, int mask, int ns, int[] memo, int[] A) {
        if (memo[mask] > 0) return memo[mask];
        if (i < 0) return 0;
        for (int slot = 1, bit = 1; slot <= ns; ++slot, bit*= 3)
            if (mask / bit % 3 > 0)
                memo[mask] = Math.max(memo[mask], (A[i] & slot) + dp(i - 1, mask - bit, ns, memo, A));
        return memo[mask];
    }

Maximum AND Sum of Array Leetcode Solution in C++

Using helper function:

    int maximumANDSum(vector<int>& A, int ns) {
        int mask = pow(3, ns) - 1;
        vector<int> memo(mask + 1, 0);
        return dp(A.size() - 1, mask, ns, memo, A);
    }
    
    int dp(int i, int mask, int ns, vector<int>& memo, vector<int>& A) {
        if (memo[mask] > 0) return memo[mask];
        if (i < 0) return 0;
        for (int slot = 1, bit = 1; slot <= ns; ++slot, bit*= 3)
            if (mask / bit % 3 > 0)
                memo[mask] = max(memo[mask], (A[i] & slot) + dp(i - 1, mask - bit, ns, memo, A));
        return memo[mask];
    }

Using lambda function:

    int maximumANDSum(vector<int>& A, int ns) {
        int mask = pow(3, ns) - 1;
        vector<int> memo(mask + 1, 0);

        function<int(int, int)> dp =
        [&](int i, int mask) {
            int& res = memo[mask];
            if (res > 0) return res;
            if (i < 0) return 0;
            for (int slot = 1, bit = 1; slot <= ns; ++slot, bit *= 3)
                if (mask / bit % 3 > 0)
                    res = max(res, (A[i] & slot) + dp(i - 1, mask - bit));
            return res;
        };

        return dp(A.size() - 1, mask);
    }

Maximum AND Sum of Array Leetcode Solution in Python 3

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        
        @cache
        def fn(k, m): 
            """Return max AND sum."""
            if k == len(nums): return 0 
            ans = 0 
            for i in range(numSlots): 
                if m & 1<<2*i == 0 or m & 1<<2*i+1 == 0: 
                    if m & 1<<2*i == 0: mm = m ^ 1<<2*i
                    else: mm = m ^ 1<<2*i+1
                    ans = max(ans, (nums[k] & i+1) + fn(k+1, mm))
            return ans 
        
        return fn(0, 0)

Maximum AND Sum of Array Leetcode Solution in Python

from functools import lru_cache, cache

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        @cache
        def dp(i=0, m1=0, m2=0): # mask1, mask2
            if i == len(nums):
                return 0
            ans = 0
            for s in range(numSlots):
                if m2 & (1 << s) == 0: # i.e. 0b0?, implying the slot is not full 
                    if m1 & (1 << s) == 0: # 0b00 + 1 => 0b01
                        nm1 = m1 | (1 << s);  nm2 = m2
                    else: # 0b01 + 1 => 0b10
                        nm1 = m1 & ~(1 << s); nm2 = m2 | (1 << s)
                    ans = max(ans, dp(i + 1, nm1, nm2) + ((s + 1) & nums[i])) # s + 1 is the actual slot no.
            return ans
        return dp()
Weekly Contest 280 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 280 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Weekly Contest 280 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Weekly Contest 280 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.