2023-03-12 contest/336 count-the-number-of-beautiful-subarrays

You are given a 0-indexed integer array nums. In one operation, you can:

Choose two different indices i and j such that 0 <= i, j < nums.length.
Choose a non-negative integer k such that the kth bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
Subtract 2k from nums[i] and nums[j].
A subarray is beautiful if it is possible to make all of its elements equal to 0 after applying the above operation any number of times.

Return the number of beautiful subarrays in the array nums.

A subarray is a contiguous non-empty sequence of elements within an array.

example

Input: nums = [4,3,1,2,4]
Output: 2
Explanation: There are 2 beautiful subarrays in nums: [4,3,1,2,4] and [4,3,1,2,4].

• We can make all elements in the subarray [3,1,2] equal to 0 in the following way:
  • Choose [3, 1, 2] and k = 1. Subtract 21 from both numbers. The subarray becomes [1, 1, 0].
  • Choose [1, 1, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 0, 0].
• We can make all elements in the subarray [4,3,1,2,4] equal to 0 in the following way:
  • Choose [4, 3, 1, 2, 4] and k = 2. Subtract 22 from both numbers. The subarray becomes [0, 3, 1, 2, 0].
  • Choose [0, 3, 1, 2, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 2, 0, 2, 0].
  • Choose [0, 2, 0, 2, 0] and k = 1. Subtract 21 from both numbers. The subarray becomes [0, 0, 0, 0, 0].

sliding window 혹은 two pointer 기법으로 주어진 배열을 탐색.
beautiful (contiguous) sub-array:
num[i], num[j] 의 bit representation 에서 index k bit 가 둘 다 1 인 경우가 존재하고 다음 operation 전에 이 공통 k 번째 비트의 값을 0 으로 바꾼다. 이것을 반복적으로 수행한 후 sub-array 의 모든 item 이 0 이라면 beatiful sub-array 가 된다.

2576. Find the Maximum Number of Marked Indices

by qeetcode

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end()); 
        int n = nums.size(), j = n-1; 
        int ans = 0; 
        for (int i = n/2-1; i >= 0; --i) {
            if (nums[i] * 2 <= nums[j]) {
                ans += 2; 
                j -= 1;
            }
        }
        return ans; 
    }
};