Largest Values From Labels

We have a set of items: the i-th item has value values[i] and label labels[i].
Then, we choose a subset S of these items, such that:
|S| <= num_wanted
For every label L, the number of items in S with label L is <= use_limit.

Return the largest possible sum of the subset S.

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.

Example 4:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.

Note:

1. 1 <= values.length == labels.length <= 20000
2. 0 <= values[i], labels[i] <= 20000
3. 1 <= num_wanted, use_limit <= values.length

Solution: 

We need to sort the values and their labels in non-ascending order and then just choose the top num_wanted based on use_limit.

For use_limit we use a count array.

Code:

Duplicate Zeros

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

-----------------------------------------------------------------------------------------------------------------

Solution:

The only catch here is to not use any extra space. The insertion should be in place. We will make use if insert property of vectors in C++ STL. Code below - 

Code:

Adding Two Negabinary Numbers

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format:  as an array of 0s and 1s, from most significant bit to least significant bit.  For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3.  A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Solution: 

Negabinary numbers are numbers with base -2.
There are three basic rules for negabinary addition (base 10 equivalent in brackets)

• 1 (1) + 1(1) = 110 (2)
• 1 (1) + 1(1) + 1(1) = 111 (3)
• 11 (-1) + 1 (1) = 0 (0)

Let's see a step by step addition of numbers in the example above - 11111 + 101
Step 1:
Adding LSB, 1+1 = 110, we have carry = 11

Step 2:
Adding next LSB + carry

Step 3:
Adding next LSB + carry








Step 4:
Adding next LSB + carry

Step 5:
Adding next LSB + carry

Step 6:
Finally the carry is 11 (-1) + 1 (1) which is equal to 0.

Code :

Flip Columns For Maximum Number of Equal Rows

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the
matrix and flip every cell in that column. Flipping a cell changes the value of that cell
from 0 to 1 or from 1 to 0.
Return the maximum number of rows that have all values equal after some
number of flips.

Example 1:
Input: [[0,1],[1,1]]
Output: 1 Explanation: After flipping no values, 1 row has all
values equal.
Example 2:
Input: [[0,1],[1,0]]
Output: 2 Explanation: After flipping values in the first column, both rows
have equal values.

Example 3:
Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2 Explanation: After flipping values in the first two columns, the last two rows
have equal values.
Note:
1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
All matrix[i].length's are equal
matrix[i][j] is 0 or 1.

Solution:

Understanding the problem-

We need to flip columns such that all values in a row are equal. i.e. all 0s or all 1s
Any Row can have all values equal after some number of flips.
eg:
[0,0,1,0,0,0,1,0] can be [0,0,0,0,0,0,0,0] after flipping 3rd and 7th columns
or
[0,0,1,0,0,0,1,0] can be [1,1,1,1,1,1,1,1] after flipping all columns except 3rd and 7th.
So, in this question if we find the rows that are equal, i.e. row[i]==row[j] where i!=j,
0<=i<=rowsize, 0<=j<=rowsize,
the maximum number of equal rows will give us maximum number of rows that have all
values equal after some flips.

When are rows equal?

Suppose, we have 3 rows r1 = [0,1,0], r2 = [0,1,0] and r3 = [1,0,1]
As we can see, r1 = r2, since all elements in r1 and r2 are same.
What if I say, r1 = r3 in this case?
We can consider r1 = r3 here, since an element can have either 0 or 1 only as its value.
In the above example if we flip all elements of r3, it will be the same as r1.

So flipping the elements in 2nd column in all the rows will result in 3 rows, each having all
their elements equal
[0,0,0], [0,0,0], [1,1,1]

The answer here will be 3.


C++ solution -