Split the Array

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Split array into two equal-length subarrays each with distinct elements. Frequency check.

Algorithm

1If n is odd: false. Count frequencies. Each frequency must be <= 2.

Common Pitfalls

•Same as LC 2965. Each element can appear at most twice (once in each half). O(n).

Split the Array.java

Java

// Approach: Check if each value's frequency <= 2 (can assign half to each part). Count unique elements.
// Time: O(n) Space: O(n)
class Solution {

    public static int countgroup(int arr[]) {
        // find xor of all elements of the array
        int allXOR = 0;
        for (int x : arr)
            allXOR ^= x;

        // 2 disjoint group out of given elements exist if XOR of array is zero
        if (allXOR != 0)
            return 0;

        // No. of disjoint sets of a set = 2^(n-1)-1
        // where n = size of set or array
        int n = arr.length;
        long MOD = 1000000007;
        return (int) (((1 << (n - 1)) - 1) % MOD);
    }
}

Was this solution helpful?