Weekly Contest 288 Leetcode Solutions

Problem 1 – Largest Number After Digit Swaps by Parity LeetCode Solution

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

  • 1 <= num <= 109

Largest Number After Digit Swaps by Parity LeetCode Solution in C++

class Solution {
public:
    int largestInteger(int num) {
        priority_queue<int> p; // priority queue to store odd digits in descending order
        priority_queue<int> q; // priority queue to store even digits in descending order
        string nums=to_string(num); // converting num to a string for easy access of the digits
        int n=nums.size(); // n stores the number of digits in num
        
        for(int i=0;i<n;i++){
            int digit=nums[i]-'0'; 
            if((digit)%2) // if digit is odd, push it into priority queue p
                p.push(digit);
            else
                q.push(digit); // if digit is even, push it into priority queue q
        }
        
        int answer=0;
        for(int i=0; i<n; i++){
            answer=answer*10;
            if((nums[i]-'0')%2) // if the digit is odd, add the largest odd digit of p into the answer
                {answer+=p.top();p.pop();}
            else
                {answer+=q.top();q.pop();} // if the digit is even, add the largest even digit of q into the answer
        }
        return answer;
    }
};

Largest Number After Digit Swaps by Parity LeetCode Solution in Java

 public int largestInteger(int n){
        char[] a = String.valueOf(n).toCharArray();
        for(int i = 0; i < a.length; i++)
            for(int j = i + 1; j < a.length; j++)
                if(a[j] > a[i] && (a[j] - a[i]) % 2 == 0){
                    char t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
        return Integer.parseInt(new String(a));
    }

Largest Number After Digit Swaps by Parity LeetCode Solution in Python

class Solution:
    def largestInteger(self, num: int):
        n = len(str(num))
        arr = [int(i) for i in str(num)]
        odd, even = [], []
        for i in arr:
            if i % 2 == 0:
                even.append(i)
            else:
                odd.append(i)
        odd.sort()
        even.sort()
        res = 0
        for i in range(n):
            if arr[i] % 2 == 0:
                res = res*10 + even.pop()
            else:
                res = res*10 + odd.pop()
        return res

Largest Number After Digit Swaps by Parity LeetCode Solution in Python3

class Solution:
    def largestInteger(self, num: int):
        n = len(str(num))
        arr = [int(i) for i in str(num)]
        odd, even = [], []
        for i in arr:
            if i % 2 == 0:
                even.append(i)
            else:
                odd.append(i)
        odd.sort()
        even.sort()
        res = 0
        for i in range(n):
            if arr[i] % 2 == 0:
                res = res*10 + even.pop()
            else:
                res = res*10 + odd.pop()
        return res

Problem 2 – Minimize Result by Adding Parentheses to Expression Leetcode Solution

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

Constraints:

  • 3 <= expression.length <= 10
  • expression consists of digits from '1' to '9' and '+'.
  • expression starts and ends with digits.
  • expression contains exactly one '+'.
  • The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Minimize Result by Adding Parentheses to Expression Leetcode Solution in Java

public String minimizeResult(String str) {
        int n=str.length();
        int idx=0;
        while(idx<n && str.charAt(idx)!='+') idx++;
        idx++;
        int ans=1000000000;
        String res="";
        for(int i=0;i<idx-1;i++){
            for(int j=idx;j<n;j++){
                StringBuilder sb=new StringBuilder(str);
                sb.insert(j+1,')');
                sb.insert(i,'(');
                
                int a=0,b=0,c=0,d=0,k=0;
                for(;sb.charAt(k)!='(';k++){
                    a=a*10+(sb.charAt(k)-'0');
                }
                k++;
                for(;sb.charAt(k)!='+';k++){
                    b=b*10+(sb.charAt(k)-'0');
                }
                k++;
                for(;sb.charAt(k)!=')';k++){
                    c=c*10+(sb.charAt(k)-'0');
                }
                k++;
                for(;k<sb.length();k++){
                    d=d*10+(sb.charAt(k)-'0');
                }
                b=b+c;
                if(a==0) a=1;
                if(d==0) d=1;
                
                int abc=a*b*d;
                if(abc<ans){
                    res=sb.toString();
                    ans=abc;
                }
            }
        }
        return res;
    }

Minimize Result by Adding Parentheses to Expression Leetcode Solution in C++

string minimizeResult(string str) {
        int n=str.length();
        int idx=0;
        while(idx<n && str[idx]!='+') idx++;
        idx++;
        int ans=1000000000;
        string res="";
        for(int i=0;i<idx-1;i++){
            for(int j=idx;j<n;j++){
                string sb=str.substr(0,i) + "(" + str.substr(i,j+1-i) + ")" +str.substr(j+1,n);
                
                int a=0,b=0,c=0,d=0,k=0;
                for(;sb[k]!='(';k++){
                    a=a*10+(sb[k]-'0');
                }
                k++;
                for(;sb[k]!='+';k++){
                    b=b*10+(sb[k]-'0');
                }
                k++;
                for(;sb[k]!=')';k++){
                    c=c*10+(sb[k]-'0');
                }
                k++;
                for(;k<sb.length();k++){
                    d=d*10+(sb[k]-'0');
                }
                b=b+c;
                if(a==0) a=1;
                if(d==0) d=1;
                
                int abc=a*b*d;
                if(abc<ans){
                    res=sb;
                    ans=abc;
                }
            }
        }
        return res;
    }

Minimize Result by Adding Parentheses to Expression Leetcode Solution in Python

class Solution:
    def minimizeResult(self, expression: str) -> str:
        plus_index, n, ans = expression.find('+'), len(expression), [float(inf),expression] 
        def evaluate(exps: str):
            return eval(exps.replace('(','*(').replace(')', ')*').lstrip('*').rstrip('*'))
        for l in range(plus_index):
            for r in range(plus_index+1, n):
                exps = f'{expression[:l]}({expression[l:plus_index]}+{expression[plus_index+1:r+1]}){expression[r+1:n]}'
                res = evaluate(exps)
                if ans[0] > res:
                    ans[0], ans[1] = res, exps
        return ans[1]

Minimize Result by Adding Parentheses to Expression Leetcode Solution in JavaScript

/**
 * @param {string} expression
 * @return {string}
 */
var minimizeResult = function(expression) {
    const [left, right] = expression.split("+");
    let res = [`(${expression})`, +left + +right];
    
    for(let i = 0; i < left.length; i++) {
        const i1 = left.slice(0, i) || 1;
        const i2 = left.slice(i);
        
        for(let j = 1; j <= right.length; j++) {
            const j1 = right.slice(0, j);
            const j2 = right.slice(j) || 1;

            const tempTotal = i1*(+i2 + +j1)*j2;
                        
            if(res[1] > tempTotal ) {
                res[0] = `${left.slice(0, i)}(${i2}+${j1})${right.slice(j)}`;
                res[1] = tempTotal
            }
        }
    }
    return res[0]
};

Problem 3 – Maximum Product After K Increments Leetcode Solution

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 109 + 7. Note that you should maximize the product before taking the modulo. 

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

  • 1 <= nums.length, k <= 105
  • 0 <= nums[i] <= 106

Maximum Product After K Increments Leetcode Solution in C++

```
int maximumProduct(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    long long ans=1, MOD = 1e9+7;
    if(nums.size()==1){
        ans=(k+nums[0])%MOD;
        return ans;
    }
    for(auto ele:nums) pq.push(ele);
    while(k) {
        int x = pq.top(); pq.pop();
        int y=pq.top(); pq.pop();
        int diff=min(k,y-x+1);
        x+=diff;
        k-=diff;
        pq.push(x);
        pq.push(y);
    }
    while(!pq.empty()) {
        int x = pq.top(); pq.pop();
        ans = (ans*x)%MOD;
    }
    return ans;
}
```

Maximum Product After K Increments Leetcode Solution in Java

public int maximumProduct(int[] nums, int k) {
        int n=nums.length;
        long mod=1000000007;
        if(n==1){
            long ans=(nums[0]+k)%mod;
            return (int)ans;
        }
        PriorityQueue<Long> pq=new PriorityQueue<>();
        for(int a:nums){
            pq.add((long)a);
        }
        while(k>0){
            long num1=pq.remove();
            long num2=pq.remove();
            long diff=Math.min(k,(num2-num1)+1);
            num1+=diff;
            k-=diff;
            pq.add(num1);
            pq.add(num2);
        }
        long ans=1;
        while(!pq.isEmpty()){
            ans=(ans*pq.remove())%mod;
        }
        return (int)ans;
    }

Maximum Product After K Increments Leetcode Solution in Python

import heapq

class Solution:
    def maximumProduct(self, nums, k: int) -> int:
        
        # creating a heap
        heap = []
        for i in nums:
            heapq.heappush (heap,i)
            
            
        # basic idea here is keep on incrementing smallest number, then only multiplication of that number will be greater
        # so basically till I have operations left I will increment my smallest number
        while k :
            current = heapq.heappop(heap)
            heapq.heappush(heap, current+1)
            k-=1
            
        result =1
        
        # Just Multiply all the numbers in heap and return the value
        while len(heap)>0:
            x= heapq.heappop(heap)
            result =(result*x )% (10**9+7)
            
        return result

Problem 4 – Maximum Total Beauty of the Gardens Leetcode Solution

Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens.

You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the ith garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers targetfull, and partial.

A garden is considered complete if it has at least target flowers. The total beauty of the gardens is then determined as the sum of the following:

  • The number of complete gardens multiplied by full.
  • The minimum number of flowers in any of the incomplete gardens multiplied by partial. If there are no incomplete gardens, then this value will be 0.

Return the maximum total beauty that Alice can obtain after planting at most newFlowers flowers.

Example 1:

Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
Output: 14
Explanation: Alice can plant
- 2 flowers in the 0th garden
- 3 flowers in the 1st garden
- 1 flower in the 2nd garden
- 1 flower in the 3rd garden
The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers.
There is 1 garden that is complete.
The minimum number of flowers in the incomplete gardens is 2.
Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14.
No other way of planting flowers can obtain a total beauty higher than 14.

Example 2:

Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
Output: 30
Explanation: Alice can plant
- 3 flowers in the 0th garden
- 0 flowers in the 1st garden
- 0 flowers in the 2nd garden
- 2 flowers in the 3rd garden
The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers.
There are 3 gardens that are complete.
The minimum number of flowers in the incomplete gardens is 4.
Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30.
No other way of planting flowers can obtain a total beauty higher than 30.
Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.

Constraints:

  • 1 <= flowers.length <= 105
  • 1 <= flowers[i], target <= 105
  • 1 <= newFlowers <= 1010
  • 1 <= full, partial <= 105

Maximum Total Beauty of the Gardens Leetcode Solution in Python

class Solution:
    def maximumBeauty(self, A: List[int], new: int, t: int, full: int, part: int) -> int:
        A = [min(t, a) for a in A]
        A.sort()
		
		# Two edge cases
        if min(A) == t: return full * len(A)
        if new >= t * len(A) - sum(A):
            return max(full*len(A), full*(len(A)-1) + part*(t-1))
        
		# Build the array `cost`.
        cost = [0]
        for i in range(1, len(A)):
            pre = cost[-1]
            cost.append(pre + i * (A[i] - A[i - 1]))

		# Since there might be some gardens having `target` flowers already, we will skip them.
        j = len(A) - 1
        while A[j] == t:
            j -= 1
        
		# Start the iteration
        ans = 0
        while new >= 0:
		
			# idx stands for the first `j` gardens, notice a edge case might happen.
            idx = min(j, bisect_right(cost, new) - 1)
			
			# bar is the current minimum flower in the incomplete garden
            bar = A[idx] + (new - cost[idx]) // (idx + 1)
			
            ans = max(ans, bar * part + full *(len(A) - j - 1))
            
			# Now we would like to complete garden j, thus deduct the cost for garden j 
			# from new and move on to the previous(next) incomplete garden!
			new -= (t - A[j])
            j -= 1
            
        return ans

Maximum Total Beauty of the Gardens Leetcode Solution in C++

long long maximumBeauty(vector<int>& fl, long long newFlowers, int target, int full, int partial) {
    sort(begin(fl), end(fl), greater<int>());
    long long p1 = 0, sum = 0, res = 0, sz = fl.size();
    for (; p1 < sz; ++p1) {
        if (target - fl[p1] > newFlowers)
            break;
        newFlowers -= max(0, target - fl[p1]);
    }
    if (p1 == sz)
        return max(sz * full, (sz - 1) * full + (fl.back() < target ? (long long)(target - 1) * partial : full));
    for (long long minF = fl.back(), p2 = fl.size() - 1; minF < target; ) {
        while (p2 >= p1 && fl[p2] <= minF)
            sum += fl[p2--];
        int needed = (sz - p2 - 1) * minF - sum;
        if (needed > newFlowers) {
            if (--p1 < 0)
                break;
            newFlowers += max(0, target - fl[p1]);
        }
        else {
            res = max(p1 * full + minF * partial, res);    
            ++minF;
        }
    }
    return res;
}

Maximum Total Beauty of the Gardens Leetcode Solution in Java

class Solution {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        int n = flowers.length;
        long[] prefix = new long[n + 1];
        Arrays.sort(flowers);
        for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + Math.min(flowers[i], target);
        long res = 0;
        for (int c = 0, i = n - 1; c <= n; ++c) {
            long remain = prefix[n] - prefix[n - c] + newFlowers - c * (long) target, min = 0;
            if (0 > remain) break;
            i = Math.min(i, n - c - 1);
            while (0 <= i && (target <= flowers[i] || flowers[i] * (long) (i + 1) - prefix[i + 1] > remain)) i--;
            if (0 <= i) {
                long dif = flowers[i] * (long) (i + 1) - prefix[i + 1];
                min = Math.min(target - 1, flowers[i] + (remain - dif) / (i + 1));
                if (i + 1 < n - c) min = Math.min(min, flowers[i + 1]);
            }
            res = Math.max(res, c * (long) full + min * (long) partial);
        }
        return res;
    }
}
Weekly Contest 288 Leetcode Solutions Review:

In our experience, we suggest you solve this Weekly Contest 288 Leetcode Solutions 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 288 Leetcode Solutions

Find on LeetCode

Conclusion:

I hope this Weekly Contest 288 Leetcode Solutions 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.