Meaning of Question

gived a sequence with n length, need to element in array divide by 2, make the sequence contains from 1 to n. determinate if can be, if it can print "YES", "NO" otherwise.

Intuition

We can sort the sequence with decreasing, then judge n if can obtain, the n — 1, n — 2, ... , 1. since that we can avoid repeative calculation. for maximum element in sequence. wo loop through divide by 2 operation unti the element is 0, in addtion, we use bool array to store n whether used?

JAVA

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            Integer nums[] = new Integer[n];
            boolean used[] = new boolean[n + 1]; // judge ith element if can obtain
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            Arrays.sort(nums, (a, b) -> b - a);
            boolean isOk = true;
            for (int i = 0; i < n; i++) {
                int x = nums[i];
                while (x > n || used[x]) // obtain x closest and less than n or x has ben used  
                    x /= 2;
                if (x > 0) used[x] = true;
                else {
                    isOk = false;
                    break;
                }
            }
            System.out.println(isOk ? "YES" : "NO");
        }
    }

CPP

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    scanf("%d", &t);
//    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> nums(n), used(n + 1);
        for (auto &i : nums) {
            scanf("%d", &i);
        }
        sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; });
        bool isOk = true;
        for (auto &num : nums) {
            int x = num;
            while (x > n || used[x]) {
                x /= 2;
            }
            if (x) used[x] = 1;
            else {
                isOk = false;
                break;
            }
        }
        printf("%s\n", isOk ? "YES" : "NO");
    }
}