Doing Smart Work

Problem Overview

• Find the minimum possible integer by swapping adjacent digits only when their parities differ, repeating as needed.
• Input: t test cases; each provides an n-digit number (leading zeros allowed). Output: the minimal achievable number (leading zeros allowed).
• Models constrained digit reordering in number manipulation, relevant to string/array processing.
• Constraints: 1 ≤ t ≤ 1e4, 1 ≤ n ≤ 1e5, sum of n across tests ≤ 1e15.
• A Rubrik interviews coding interview problem and common interview question.