304 North Cardinal St.
Dorchester Center, MA 02124

# 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) {
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*/
}
}
``````

### Merge Nodes in Between Zeros Leetcode Solution in Java

``````    public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(Integer.MIN_VALUE), prev = dummy;
prev.next = head; // prev connects next 0 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.
}
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)
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]:
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
``````

## 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()){
}
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{
}
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 =  * 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