LeetCode-in-Java

3897. Maximum Value of Concatenated Binary Segments

Hard

You are given two integer arrays nums1 and nums0, each of size n.

• nums1[i] represents the number of '1's in the ith segment.
• nums0[i] represents the number of '0's in the ith segment.

For each index i, construct a binary segment consisting of:

• nums1[i] occurrences of '1' followed by
• nums0[i] occurrences of '0'.

You may rearrange the order of these segments in any way. After rearranging, concatenate all segments to form a single binary string.

Return the maximum possible integer value of the concatenated binary string.

Since the result can be very large, return the answer modulo 109 + 7.

Example 1:

Input: nums1 = [1,2], nums0 = [1,0]

Output: 14

Explanation:

• At index 0, nums1[0] = 1 and nums0[0] = 1, so the segment formed is "10".
• At index 1, nums1[1] = 2 and nums0[1] = 0, so the segment formed is "11".
• Reordering the segments as "11" followed by "10" produces the binary string "1110".
• The binary number "1110" has value 14 which is the maximum possible value.

Example 2:

Input: nums1 = [3,1], nums0 = [0,3]

Output: 120

Explanation:

• At index 0, nums1[0] = 3 and nums0[0] = 0, so the segment formed is "111".
• At index 1, nums1[1] = 1 and nums0[1] = 3, so the segment formed is "1000".
• Reordering the segments as "111" followed by "1000" produces the binary string "1111000".
• The binary number "1111000" has value 120 which is the maximum possible value.

Constraints:

• 1 <= n == nums1.length == nums0.length <= 105
• 0 <= nums1[i], nums0[i] <= 104
• nums1[i] + nums0[i] > 0
• The total sum of all elements in nums1 and nums0 does not exceed 2 * 10⁵.

Solution

import java.util.Arrays;

public class Solution {
    private static final int MOD = (int) 1e9 + 7;
    private static final int N = 10001;
    private static final int[] POW2 = new int[N];

    static {
        POW2[0] = 1;
        for (int i = 1; i < N; i++) {
            POW2[i] = POW2[i - 1] * 2 % MOD;
        }
    }

    public int maxValue(int[] nums1, int[] nums0) {
        int n = nums0.length;
        Integer[] indices = new Integer[n];
        int size = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (nums0[i] == 0) {
                count += nums1[i];
            } else {
                indices[size++] = i;
            }
        }
        Arrays.sort(
                indices,
                0,
                size,
                (i, j) -> nums1[i] == nums1[j] ? nums0[i] - nums0[j] : nums1[j] - nums1[i]);
        long ans = pow(2, count) - 1;
        for (int i = 0; i < size; ++i) {
            int index = indices[i];
            int count1 = nums1[index];
            int count0 = nums0[index];
            ans = (ans * POW2[count1] + POW2[count1] - 1) % MOD * POW2[count0] % MOD;
        }
        return (int) ans;
    }

    private long pow(long x, int n) {
        long result = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                result = result * x % MOD;
            }
            x = x * x % MOD;
            n >>= 1;
        }
        return result;
    }
}

This site is open source. Improve this page.