304 North Cardinal St.
Dorchester Center, MA 02124

# Weekly Contest 279 LeetCode Solution

## Problem 1 – Sort Even and Odd Indices Independently Leetcode Solution

You are given a 0-indexed integer array `nums`. Rearrange the values of `nums` according to the following rules:

1. Sort the values at odd indices of `nums` in non-increasing order.
• For example, if `nums = [4,1,2,3]` before this step, it becomes `[4,3,2,1]` after. The values at odd indices `1` and `3` are sorted in non-increasing order.
2. Sort the values at even indices of `nums` in non-decreasing order.
• For example, if `nums = [4,1,2,3]` before this step, it becomes `[2,1,4,3]` after. The values at even indices `0` and `2` are sorted in non-decreasing order.

Return the array formed after rearranging the values of `nums`.

Example 1:

``````Input: nums = [4,1,2,3]
Output: [2,3,4,1]
Explanation:
First, we sort the values present at odd indices (1 and 3) in non-increasing order.
So, nums changes from [4,1,2,3] to [4,3,2,1].
Next, we sort the values present at even indices (0 and 2) in non-decreasing order.
So, nums changes from [4,1,2,3] to [2,3,4,1].
Thus, the array formed after rearranging the values is [2,3,4,1].
``````

Example 2:

``````Input: nums = [2,1]
Output: [2,1]
Explanation:
Since there is exactly one odd index and one even index, no rearrangement of values takes place.
The resultant array formed is [2,1], which is the same as the initial array.
``````

Constraints:

• `1 <= nums.length <= 100`
• `1 <= nums[i] <= 100`

### Sort Even and Odd Indices Independently Leetcode Solution in Python

``````    def sortEvenOdd(self, A):
A[::2], A[1::2] = sorted(A[::2]), sorted(A[1::2])[::-1]
return A
``````

### Sort Even and Odd Indices Independently Leetcode Solution in Java

Counting Sort:

``````class Solution {
public int[] sortEvenOdd(int[] nums) {
int[] even = new int;
int[] odd = new int;
int length = nums.length;
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
even[nums[i]]++;
} else {
odd[nums[i]]++;
}
}
int e = 0;
int o = 100;
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
// check even
while (even[e] == 0) {
++e;
}
nums[i] = e;
even[e]--;
} else {
while(odd[o] == 0) {
--o;
}
nums[i] = o;
odd[o]--;
}
}
return nums;
}
}
``````

Heap:

``````class Solution {
public int[] sortEvenOdd(int[] nums) {
PriorityQueue<Integer> even = new PriorityQueue<>((a, b)->(a - b));
PriorityQueue<Integer> odd = new PriorityQueue<>((a, b)->(b - a));
int length = nums.length;
for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
} else {
}
}

for (int i = 0; i < length; ++i) {
if (i % 2 == 0) {
nums[i] = even.poll();
} else {
nums[i] = odd.poll();
}
}
return nums;
}
}
``````

### Sort Even and Odd Indices Independently Leetcode Solution in C++

``````class Solution {
public:
vector<int> sortEvenOdd(vector<int>& nums) {
int n = nums.size();
priority_queue<int> maxheap;
priority_queue <int, vector<int>, greater<int> > minheap;

// even fill  (0,2,4,6....)
for(int i=0; i<n;){
minheap.push(nums[i]);
i = i+2;
}
// odd fill  (1,3,5,7,....)
for(int i=1; i<n;){
maxheap.push(nums[i]);
i = i+2;
}
//
// nums.clear();
int i = 0;
while(i<n){
if(i%2==0){
nums[i] = minheap.top();
minheap.pop();
}
else{
nums[i] = maxheap.top();
maxheap.pop();
}
i++;
}
return nums;
}
};
``````

### Problem 2 – Smallest Value of the Rearranged Number Leetcode Solution

You are given an integer `num.` Rearrange the digits of `num` such that its value is minimized and it does not contain any leading zeros.

Return the rearranged number with minimal value.

Note that the sign of the number does not change after rearranging the digits.

Example 1:

``````Input: num = 310
Output: 103
Explanation: The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310.
The arrangement with the smallest value that does not contain any leading zeros is 103.
``````

Example 2:

``````Input: num = -7605
Output: -7650
Explanation: Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.
``````

Constraints:

• `-1015 <= num <= 1015`

### Smallest Value of the Rearranged Number Leetcode Solution in Python

``````class Solution:
def smallestNumber(self, num: int) -> int:
s = sorted(str(abs(num)), reverse = num < 0)
non_zero = next((i for i, n in enumerate(s) if n != '0'), 0)
s, s[non_zero] = s[non_zero], s
return int(''.join(s)) * (1 if num >= 0 else -1)
``````

### Smallest Value of the Rearranged Number Leetcode Solution in C++

``````long long smallestNumber(long long num) {
auto s = to_string(abs(num));
sort(begin(s), end(s), [&](int a, int b){ return num < 0 ? a > b : a < b; });
if (num > 0)
swap(s, s[s.find_first_not_of('0')]);
return stoll(s) * (num < 0 ? -1 : 1);
}
``````

### Smallest Value of the Rearranged Number Leetcode Solution in Java

``````class Solution {
public long smallestNumber(long num) {
if(num == 0){
return 0;
}
boolean isNegative = num < 0;
num  = num < 0 ? num * -1 : num;

char[] c = String.valueOf(num).toCharArray();
Arrays.sort(c);
String str;
if(!isNegative){
int non = 0;
//if not negative we need to find out the first non-leading zero then swap with first zero
for(; non < c.length; non++){
if(c[non] != '0'){
break;
}
}
char temp = c[non];
c[non] = c;
c = temp;
str = new String(c);
}else{
str = new String(c);
StringBuilder sb = new StringBuilder(str);
str = "-".concat(sb.reverse().toString());
}
return Long.valueOf(str);
}
}
``````

### Smallest Value of the Rearranged Number Leetcode Solution in JavaScript

``````var smallestNumber = function(num) {
let arr = Array.from(String(num));
if(num>0){
arr.sort((a,b)=>{
return a-b;
})
}
else{
arr.sort((a,b)=>{
return b-a;
})
}
for(let i=0;i<arr.length;i++){
if(arr[i]!=0){
[arr,arr[i]]=[arr[i],arr];
break;
}
}
return arr.join("");
};
``````

## Problem 3 – Design Bitset Leetcode Solution

Bitset is a data structure that compactly stores bits.

Implement the `Bitset` class:

• `Bitset(int size)` Initializes the Bitset with `size` bits, all of which are `0`.
• `void fix(int idx)` Updates the value of the bit at the index `idx` to `1`. If the value was already `1`, no change occurs.
• `void unfix(int idx)` Updates the value of the bit at the index `idx` to `0`. If the value was already `0`, no change occurs.
• `void flip()` Flips the values of each bit in the Bitset. In other words, all bits with value `0` will now have value `1` and vice versa.
• `boolean all()` Checks if the value of each bit in the Bitset is `1`. Returns `true` if it satisfies the condition, `false` otherwise.
• `boolean one()` Checks if there is at least one bit in the Bitset with value `1`. Returns `true` if it satisfies the condition, `false` otherwise.
• `int count()` Returns the total number of bits in the Bitset which have value `1`.
• `String toString()` Returns the current composition of the Bitset. Note that in the resultant string, the character at the `ith` index should coincide with the value at the `ith` bit of the Bitset.

Example 1:

``````Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[, , , [], [], , [], [], , [], []]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]

Explanation
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // the value at idx = 3 is updated to 1, so bitset = "00010".
bs.fix(1);     // the value at idx = 1 is updated to 1, so bitset = "01010".
bs.flip();     // the value of each bit is flipped, so bitset = "10101".
bs.all();      // return False, as not all values of the bitset are 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "00101".
bs.flip();     // the value of each bit is flipped, so bitset = "11010".
bs.one();      // return True, as there is at least 1 index with value 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "01010".
bs.count();    // return 2, as there are 2 bits with value 1.
bs.toString(); // return "01010", which is the composition of bitset.
``````

Constraints:

• `1 <= size <= 105`
• `0 <= idx <= size - 1`
• At most `105` calls will be made in total to `fix``unfix``flip``all``one``count`, and `toString`.
• At least one call will be made to `all``one``count`, or `toString`.
• At most `5` calls will be made to `toString`.

### Design Bitset Leetcode Solution in Java

``````class Bitset {
int size;
Set<Integer> one = new HashSet<>();
Set<Integer> zero = new HashSet<>();
public Bitset(int size) {
this.size = size;
}

public void fix(int idx) {
zero.remove(idx);
}

public void unfix(int idx) {
one.remove(idx);
}

//swapping object's referrence is O(1)
public void flip() {
Set<Integer> s = one;
one = zero;
zero = s;
}

public boolean all() {
return one.size() == size;
}

public boolean one() {
return one.size()>=1;
}

public int count() {
return one.size();
}

public String toString() {
StringBuilder sb=  new StringBuilder();
for(int i=0;i<size;i++) {
if(one.contains(i)) sb.append("1");
else if(zero.contains(i)) sb.append("0");
}
return sb.toString();
}
}
``````

### Design Bitset Leetcode Solution in C++

``````    int a = 0, sz = 0, cnt = 0, isFlip = 0;
string s;
Bitset(int size) {
sz = size;
s = string(sz, '0');
}

void fix(int idx) {
if (s[idx] == '0' + isFlip) {
s[idx] = '1' + '0' - s[idx];
cnt++;
}
}

void unfix(int idx) {
if (s[idx] == '1' - isFlip) {
s[idx] = '1' + '0' - s[idx];
cnt--;
}
}

void flip() {
isFlip ^= 1;
cnt = sz - cnt;
}

bool all() {
return cnt == sz;
}

bool one() {
return cnt > 0;
}

int count() {
return cnt;
}

string toString() {
if (isFlip) {
string s2 = s;
for (auto& c: s2)
c = '0' + '1' - c;
return s2;
}
return s;
}
``````

### Design Bitset Leetcode Solution in Python

``````class Bitset(object):

def __init__(self, size):
self.a = 0
self.size = size
self.cnt = 0

def fix(self, idx):
if self.a & (1 << idx) == 0:
self.a |= 1 << idx
self.cnt += 1

def unfix(self, idx):
if self.a & (1 << idx):
self.a ^= 1 << idx
self.cnt -= 1

def flip(self):
self.a ^= (1 << self.size) - 1
self.cnt = self.size - self.cnt

def all(self):
return self.cnt == self.size

def one(self):
return self.a > 0

def count(self):
return self.cnt

def toString(self):
a = bin(self.a)[2:]
return a[::-1] + '0' * (self.size - len(a))
``````

### Design Bitset Leetcode Solution in Python 3

``````    def __init__(self, size: int):
self.sz = size
self.bits = [False] * size
self.flipped = [True] * size
self.bitCount = 0

def fix(self, idx: int) -> None:
if not self.bits[idx]:
self.bits[idx] ^= True
self.flipped[idx] ^= True
self.bitCount += 1

def unfix(self, idx: int) -> None:
if self.bits[idx]:
self.bits[idx] ^= True
self.flipped[idx] ^= True
self.bitCount -= 1

def flip(self) -> None:
self.bits, self.flipped = self.flipped, self.bits
self.bitCount = self.sz - self.bitCount

def all(self) -> bool:
return self.sz == self.bitCount

def one(self) -> bool:
return self.bitCount > 0

def count(self) -> int:
return self.bitCount

def toString(self) -> str:
return ''.join(['1' if b else '0' for b in self.bits])
``````

### Problem 4 – Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution

You are given a 0-indexed binary string `s` which represents a sequence of train cars. `s[i] = '0'` denotes that the `ith` car does not contain illegal goods and `s[i] = '1'` denotes that the `ith` car does contain illegal goods.

As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:

1. Remove a train car from the left end (i.e., remove `s`) which takes 1 unit of time.
2. Remove a train car from the right end (i.e., remove `s[s.length - 1]`) which takes 1 unit of time.
3. Remove a train car from anywhere in the sequence which takes 2 units of time.

Return the minimum time to remove all the cars containing illegal goods.

Note that an empty sequence of cars is considered to have no cars containing illegal goods.

Example 1:

``````Input: s = "1100101"
Output: 5
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5.

An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.

5 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.
``````

Example 2:

``````Input: s = "0010"
Output: 2
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.

Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.

Another way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2.
This obtains a total time of 2.

2 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.
``````

Constraints:

• `1 <= s.length <= 2 * 105`
• `s[i]` is either `'0'` or `'1'`.

### Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in

``````    public int minimumTime(String s) {
int n = s.length(), left = 0, res = n;
for (int i = 0; i < n; ++i) {
left = Math.min(left + (s.charAt(i) - '0') * 2, i + 1);
res = Math.min(res, left + n - 1 - i);
}
return res;
}
``````

### Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in C++

``````    int minimumTime(string s) {
int n = s.size(), left = 0, res = n;
for (int i = 0; i < n; ++i) {
left = min(left + (s[i] - '0') * 2, i + 1);
res = min(res, left + n - 1 - i);
}
return res;
}
``````

### Minimum Time to Remove All Cars Containing Illegal Goods Leetcode Solution in Python

``````    def minimumTime(self, s):
left, res, n = 0, len(s), len(s)
for i,c in enumerate(s):
left = min(left + (c == '1') * 2, i + 1)
res = min(res, left + n - 1 - i)
return res
``````
##### Weekly Contest 279 LeetCode Solution Review:

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

Find on LeetCode

##### Conclusion:

I hope this Weekly Contest 279 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