Feasibility of a Uniform-Parity Construction

### Problem You are given an array `nums1` of distinct positive integers. Determine whether another array `nums2` of the same length can be constructed so that its values are all odd or all even. For each index `i`, choose exactly one of these definitions, in any order: - Keep the original value: `nums2[i] = nums1[i]`. - Choose an index `j != i` and use `nums2[i] = nums1[i] - nums1[j]`. All references use the original `nums1` values. A reference index may be used for more than one different output position. The constructed values are not required to be positive or distinct; they must satisfy the chosen operations and uniform parity. Return `true` if construction is possible, otherwise `false`. ```cpp class Solution { public: bool uniformArray(vector<int>& nums1); }; ``` ### Examples **Example 1:** ```text Input: nums1 = [2,7,10] Output: true Explanation: Choose nums2 = [2-7,7,10-7] = [-5,7,3]. Each index uses exactly one permitted definition, and all three values are odd. The reference index for 7 is different from both indices using subtraction. ``` **Example 2:** ```text Input: nums1 = [4] Output: true Explanation: Keeping its only value constructs [4], whose values are all even. No distinct reference index is needed for the keep option. ``` ### Constraints - `1 <= nums1.length <= 100`. - `1 <= nums1[i] <= 100`. - All original values are distinct. ### Clarifying Questions - Must each index choose one of the two definitions? Yes. - May a subtraction use `j=i`? No. - Can a constructed value be negative? Yes; only the original input has the stated positivity bound. - Are earlier constructed `nums2` values used in later subtractions? No; the formulas refer to `nums1`. - Is the constructed array returned? No; the API returns only feasibility. ### What a Strong Answer Covers - The exact per-index choices and the different-reference-index requirement. - Uniform output parity without extra output positivity or uniqueness restrictions. - A complete feasibility argument for every valid input, including a singleton. - Correct Boolean output, numeric safety, and resource analysis. ### Follow-up Questions - How would requesting a witness array change the output contract? - What additional information would an output listing each chosen operation need to contain? ```hint Separate the case with no odd input value If all original values are even, consider keeping them. Otherwise choose one original odd value, keep odd entries, and consider subtracting that odd value from even entries. Check why the different-index requirement holds and why a negative result is still permitted. ```