Maximum value of concatenated binary segments

26.7% acceptance

May 13, 2026

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_value(nums1: Vec<i32>, nums0: Vec<i32>) -> i32 {
    const M: u64 = 1_000_000_007;
    let n = nums1.len();
    let total_len: usize = nums1.iter().chain(nums0.iter())
      .map(|&x| x as usize).sum();
    let mut pow2 = vec![1u64; total_len + 2];
    for i in 1..pow2.len() {
      pow2[i] = pow2[i - 1] * 2 % M;
    }
    let segs: Vec<(usize, usize)> = nums1.iter().zip(nums0.iter())
      .map(|(&a, &b)| (a as usize, b as usize))
      .collect();
    let strs: Vec<Vec<u8>> = segs.iter().map(|&(a, b)| {
      let mut v = vec![b'1'; a];
      v.resize(a + b, b'0');
      v
    }).collect();
    let mut idx: Vec<usize> = (0..n).collect();
    idx.sort_by(|&i, &j| {
      let si = &strs[i];
      let sj = &strs[j];
      for (a, b) in si.iter().chain(sj.iter()).zip(sj.iter().chain(si.iter())) {
        if a != b {
          return b.cmp(a);
        }
      }
      std::cmp::Ordering::Equal
    });
    let mut result = 0u64;
    for i in idx {
      let (a, b) = segs[i];
      let l = a + b;
      let seg_val = (pow2[a] + M - 1) % M * pow2[b] % M;
      result = (result * pow2[l] + seg_val) % M;
    }
    result as i32
  }
}