Weekly Contest 281 LeetCode Solution

Problem 1 – Count Integers With Even Digit Sum Leetcode Solution

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even.

The digit sum of a positive integer is the sum of all its digits.

Example 1:

Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.    

Example 2:

Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.

Constraints:

  • 1 <= num <= 1000

Count Integers With Even Digit Sum Leetcode Solution in C++

class Solution {
public:
    int countEven(int num) {
        int temp = num, sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum % 2 == 0 ? temp / 2 : (temp - 1) / 2;
    }
};

Count Integers With Even Digit Sum Leetcode Solution in Python 3

class Solution:
    def countEven(self, num: int) -> int:
        return num // 2 if sum([int(k) for k in str(num)]) % 2 == 0 else (num - 1) // 2

Count Integers With Even Digit Sum Leetcode Solution in Python

    def countEven(self, num: int) -> int:
        n, dSum = num, 0
        while n > 0: # Calculate digit sum of numbers
            dSum += n%10
            n = n//10
        if num % 2 == 0 and dSum % 2 == 1:
            return num//2 - 1
        return num//2

Count Integers With Even Digit Sum Leetcode Solution in Java

class Solution
{
    public int countEven(int num)
    {
        int count = 0;
        for(int i = 1; i <= num; i++)
            if(sumDig(i))
                count++;
        return count;
    }
    private boolean sumDig(int n)
    {
        int sum = 0;
        while(n > 0)
        {
            sum += n % 10;
            n /= 10;
        }
		return (sum&1) == 0 ? true : false;
    }
}

Problem 2 – Merge Nodes in Between Zeros Leetcode Solution

You are given the head of a linked list, which contains a series of integers separated by 0‘s. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0‘s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0‘s.

Return the head of the modified linked list.

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation: 
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

Constraints:

  • The number of nodes in the list is in the range [3, 2 * 105].
  • 0 <= Node.val <= 1000
  • There are no two consecutive nodes with Node.val == 0.
  • The beginning and end of the linked list have Node.val == 0.

Merge Nodes in Between Zeros Leetcode Solution in C++

 ListNode* mergeNodes(ListNode* head) {
     head=head->next;
     ListNode* start=head;
     while(start){
	    ListNode* end= start;   /* Point to first node of current part for getting sum */
        int sum=0;
        while(end->val!=0) sum+= end->val , end=end->next;
        start->val=sum;   /*assign sum to first node between two 0*/
        start->next=end->next;   /*make this connect to first node of next part*/
        start=start->next;    /*go..to..next..part*/
	 }
     return head;
}

Merge Nodes in Between Zeros Leetcode Solution in Java

    public ListNode mergeNodes(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE), prev = dummy;
        while (head != null && head.next != null) {
            prev.next = head; // prev connects next 0 node.
            head = head.next; // head forward to a non-zero node.
            while (head != null && head.val != 0) { // traverse all non-zero nodes between two zero nodes.
                prev.next.val += head.val; // add current value to the previous zero node.
                head = head.next; // forward one step.
            }
            prev = prev.next; // prev point to the summation node (initially 0).
        }
        prev.next = null; // cut off last 0 node.
        return dummy.next;
    }

Merge Nodes in Between Zeros Leetcode Solution in Python 3

    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = prev = ListNode(-math.inf)
        while head and head.next:
            prev.next = head
            head = head.next
            while head and head.val != 0:
                prev.next.val += head.val
                head = head.next
            prev = prev.next
        prev.next = None    
        return dummy.next

Merge Nodes in Between Zeros Leetcode Solution in Python

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ptr1 = head
        ptr2 = head.next
        s = 0
        while ptr2:
            if ptr2.val == 0:
                ptr1 = ptr1.next
                ptr1.val=s
                s=0
            else:
                s+=ptr2.val
            ptr2 = ptr2.next
        ptr1.next=None
        return head.next

Problem 3 – Construct String With Repeat Limit Leetcode Solution

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

  • 1 <= repeatLimit <= s.length <= 105
  • s consists of lowercase English letters.

Construct String With Repeat Limit Leetcode Solution in C++

class Solution {
public:
    string repeatLimitedString(string s, int k) { // k is the repeatLimit
        int n = s.length();
        unordered_map<char,int> m;
        for(int i=0;i<n;i++) m[s[i]]++;
        priority_queue<pair<char,int>> pq;
        for(auto i: m){
            pq.push({i.first,i.second}); // pushing the characters with their frequencies.
        }
        
        string ans = "";
        while(!pq.empty()){
            char c1 = pq.top().first;
            int n1 = pq.top().second;
            pq.pop();
                
            int len = min(k,n1); // Adding characters upto minimum of repeatLimit and present character count.
            for(int i=0;i<len;i++){ // adding the highest priority element to the ans.
                ans += c1;
            }
            
            char c2;
            int n2=0;
            if(n1-len>0){ // If the cnt of present character is more than the limit.
                if(!pq.empty()){ //Getting the next priority character.
                    c2 = pq.top().first;
                    n2 = pq.top().second;
                    pq.pop();
                }
                else{
                    return ans; // if there is no another letter to add, we just return ans.
                }
                ans += c2; // Adding next priority character to ans.
                
                // If the elements are left out, pushing them back into priority queue for next use.
                pq.push({c1,n1-len});
                if(n2-1>0) pq.push({c2,n2-1}); 
            }
        }
        return ans;
    }
};

Construct String With Repeat Limit Leetcode Solution in Java

   public String repeatLimitedString(String s, int repeatLimit) {
        PriorityQueue<Character> pq = new PriorityQueue<Character>((a,b)->b-a);
        for(char ch:s.toCharArray()){
        	pq.add(ch);
        }
        StringBuffer res = new StringBuffer();
        ArrayList<Character> list = new ArrayList<Character>();
        Stack<Character> stk = new Stack<Character>();
        int count = 0;
        char previouschar = pq.peek();
        while(!pq.isEmpty()){
        	char curr = pq.poll();
        	if(curr==previouschar){
        		if(count<repeatLimit){
        			res.append(curr);
        		}
        		else{
        			stk.add(curr);
        		}
        		count++;
        	}
        	else{
        		if(stk.isEmpty()){
        			count=0;
        			res.append(curr);
        			previouschar = curr;
        			count++;
        		}
        		else{
        			res.append(curr);
        			count=0;
        			while(!stk.isEmpty() && count<repeatLimit){
        				res.append(stk.pop());
        				count++;
        			}
        		}
        	}
        }
        return res.toString();
    }

Construct String With Repeat Limit Leetcode Solution in Python 3

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        pq = [(-ord(k), v) for k, v in Counter(s).items()] 
        heapify(pq)
        ans = []
        while pq: 
            k, v = heappop(pq)
            if ans and ans[-1] == k: 
                if not pq: break 
                kk, vv = heappop(pq)
                ans.append(kk)
                if vv-1: heappush(pq, (kk, vv-1))
                heappush(pq, (k, v))
            else: 
                m = min(v, repeatLimit)
                ans.extend([k]*m)
                if v-m: heappush(pq, (k, v-m))
        return "".join(chr(-x) for x in ans)

Construct String With Repeat Limit Leetcode Solution in Python

    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        arr = [0] * 26
        a = ord('a')
        
        for char in s:
            arr[ord(char)-a] += 1
			
        # Using an array to store the answer as appending to a string is a costly operation
        ans = []
        curr = 25
        prev = 24 
		
        # We are starting with curr = 25 as we need to add the largest character first
        while curr >= 0:
            if arr[curr] == 0:
                curr -= 1
                continue
            
			# If the character is present in the string then we add it to our answer 
            for i in range(min(repeatLimit, arr[curr])):
                ans.append(chr(curr + a))
                arr[curr] -= 1
                
			# If the above for loop was able to add all the characters then we can move on to the next one
            if arr[curr] == 0:
                curr -= 1
                continue
            
			# If the above for loop was not able to add all the characters then we need to add a second largest character before we can continue  adding the largest character to our answer again
            g = False
            for j in range(min(prev, curr-1), -1, -1):
                if arr[j]:
                    g = True
                    arr[j] -= 1
                    prev = j
                    ans.append(chr(j+a))
                    break
			# If g is false then we know that there were no other characters present other  than the largest character
            if not g: break
            
        return ''.join(ans)

Problem 4 – Count Array Pairs Divisible by K Leetcode Solution

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

  • 0 <= i < j <= n - 1 and
  • nums[i] * nums[j] is divisible by k.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation: 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.    

Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.

Constraints:

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

Count Array Pairs Divisible by K Leetcode Solution in Java

    public long countPairs(int[] nums, int k) {
        Map<Long, Long> cnt = new HashMap<>();
        long res = 0L;
        for (int x : nums) {
            cnt.merge(BigInteger.valueOf(x).gcd(BigInteger.valueOf(k)).longValue(), 1L, Long::sum);
        }
        for (long x : cnt.keySet()) {
            for (long y : cnt.keySet()) {
                if (x <= y && x * y % k == 0L) {
                    res += x < y ? cnt.get(x) * cnt.get(y) : cnt.get(x) * (cnt.get(x) - 1L) / 2L;
                }
            }
        }
        return res;
    }

Count Array Pairs Divisible by K Leetcode Solution in C++

long long coutPairs(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for (int& nu: nums) {
            mp[gcd(nu, k)]++;
        }
        long long res = 0;
        for (auto& [a, c1]: mp) {
            for (auto & [b, c2]: mp) {
                if (a <= b && a*(long) b %k == 0) {
                    res += a < b?(long)c1*c2:(long)c1*(c1-1)/2;
                }
            }
        }
        return res;    
    }

Count Array Pairs Divisible by K Leetcode Solution in Python

    def coutPairs(self, A, k):
        cnt = Counter(math.gcd(a, k) for a in A)
        res = 0
        for a in cnt:
            for b in cnt:
                if a <= b and a * b % k == 0:
                    res += cnt[a] * cnt[b] if a < b else cnt[a] * (cnt[a] - 1) // 2
        return res

Count Array Pairs Divisible by K Leetcode Solution in Python 3

class Solution:
    def coutPairs(self, nums: List[int], k: int) -> int:
        factors = []
        for x in range(1, int(sqrt(k))+1):
            if k % x == 0: factors.append(x)
        ans = 0 
        freq = Counter()
        for x in nums: 
            x = gcd(x, k)
            ans += freq[k//x]
            for f in factors: 
                if x % f == 0 and f <= x//f: 
                    freq[f] += 1
                    if f < x//f: freq[x//f] += 1
        return ans 
Weekly Contest 281 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 281 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 281 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Weekly Contest 281 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. Required fields are marked *