thảo luận Leetcode mỗi ngày

function countMaxOrSubsets(nums: number[]): number {
    let max = 0;
    for (const num of nums) {
        max |= num;
    }

    const go = (idx: number, cur: number): number =>{
        if (idx === nums.length) {
            return cur === max ? 1 : 0;
        }

        return go(idx + 1, cur | nums[idx]) + go(idx + 1, cur);
    }

    return go(0, 0);
};

var countMaxOrSubsets = function (nums) {
    const n = nums.length;
    let msf = 0, c = 0;
    const dfs = (i, bm) => {
        if (i === n) {
            if (bm > msf) {
                msf = bm;
                c = 0;
            }
            c += bm === msf ? 1 : 0;
            return;
        }
        
        dfs(i + 1, bm);
        dfs(i + 1, bm | nums[i]);
    };
    dfs(0, 0);
    return c;
};

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:       
        target, n = 0, len(nums)
        for num in nums:
            target |= num
        self.result = 0
        chosen = [0 for _ in range(n)]

        def calOrValue():
            orValue = 0
            for i in range(n):
                if chosen[i]:
                    orValue |= nums[i]
            return orValue

        def backtracking(i):
            if i == n:
                if calOrValue() == target:
                    self.result += 1
                return
            chosen[i] = 1
            backtracking(i+1)
            chosen[i] = 0
            backtracking(i+1)

        backtracking(0)
        return self.result

class Solution {
    func countMaxOrSubsets(_ nums: [Int]) -> Int {
        let max = nums.reduce(0,|)
        var result = 0
        func dfs(_ i: Int,_ pre: Int) {
            guard i < nums.count else { return }
            let cur = pre | nums[i]
            if cur == max {
                result += Int(pow(Double(2), Double(nums.count-i-1)))
            } else {
                dfs(i+1, cur)
            }
            dfs(i+1, pre)
        }
        dfs(0, 0)
  
        return result
    }
}

class Solution {
    int ans;
    public int countMaxOrSubsets(int[] nums) {
        int max = 0;
        int bitwise = 0;
        ans = 0;
        for (int i = 0; i < nums.length; i++) {
            bitwise |= nums[i];
            max = Math.max(max, bitwise);
        }
        backtrack(0, nums, 0, max);
        return ans;
    }

    private void backtrack(int index, int[] nums, int curr, int max) {
        if (index == nums.length) {
            if (curr == max) ans++;
            return;
        }
        backtrack(index + 1, nums, curr | nums[index], max);
        backtrack(index + 1, nums, curr, max);
    }
}

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        maxx = nums[0]
        for i in range(1, len(nums)):
            maxx = maxx | nums[i]

        res = 0
        def maxOr(i, curr):
            nonlocal res

            if i >= len(nums):
                return
           
            tmp = curr
            curr = curr | nums[i]
            if curr == maxx:
                res += 1
           
            # Use nums[i]
            maxOr(i + 1, curr)
            # Ignore nums[i]
            maxOr(i + 1, tmp)

        maxOr(0, 0)

        return res

class Solution {
    int ans = 0;
    public int countMaxOrSubsets(int[] nums) {
        int max = 0;
        for(int num : nums) {
            max |= num;
        }
        backTrack(nums, 0, 0, max);
        return ans;
    }
    public void backTrack(int[] nums, int index,int bitwise, int max) {
        if(bitwise == max ) ans++;
        for(int i = index; i < nums.length; i++) {
            backTrack(nums, i + 1,bitwise | nums[i], max);
        }
    }
}

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        # Step 1: Find the maximum bitwise OR of all elements
        max_or = 0
        for num in nums:
            max_or |= num
       
        # Step 2: Initialize count of subsets with maximum OR
        count = 0

        # Helper function for backtracking
        def backtrack(index, curr_or):
            nonlocal count
           
            # If we reach the end of the array, check if the current OR equals the max OR
            if index == len(nums):
                if curr_or == max_or:
                    count += 1
                return

            # Option 1: Include the current element in the subset
            backtrack(index + 1, curr_or | nums[index])

            # Option 2: Exclude the current element from the subset
            backtrack(index + 1, curr_or)
       
        # Start backtracking from index 0 and an initial OR of 0
        backtrack(0, 0)

        return count

class Solution {
private:
    int maxOr = 0; vector<unordered_map<int, int>> dp{}; 
    int count(const vector<int>& nums, vector<int>::const_iterator iter, int accOr, vector<unordered_map<int,int>>::iterator dp) {
        if (accOr == maxOr) return 1 << distance(iter, nums.end());
        if (iter == nums.end()) return 0;
        if ((*dp).find(accOr) == (*dp).end()) {
            (*dp)[accOr] = count(nums, iter + 1, *iter | accOr, dp + 1) + count(nums, iter + 1, accOr, dp + 1);
        }
        return (*dp)[accOr];
    }
public:
    int countMaxOrSubsets(vector<int>& nums) {
        for (auto& num : nums) maxOr |= num;
        dp = vector<unordered_map<int, int>>(nums.size(), unordered_map<int, int>{});
        return count(nums, nums.begin(), 0, dp.begin());
    }
};

class Solution {
    int[] memo;
    public int countMaxOrSubsets(int[] nums) {
        int maxOr = 0;

        for (int num : nums) {
            maxOr |= num;
        }

        return backtrack(nums, 0, 0, maxOr);
    }

    private int backtrack(int[] nums, int curr, int sumOr, int maxOr) {
        if (sumOr > maxOr || curr == nums.length) {
            return 0;
        }

        return backtrack(nums, curr + 1, sumOr | nums[curr], maxOr)
        + backtrack(nums, curr + 1, sumOr, maxOr)
        + ((sumOr | nums[curr]) == maxOr ? 1 : 0);
    }
}

class Solution {
    int max =0;
    int res=0;
    public int countMaxOrSubsets(int[] nums) {
        backtrack(nums, 0, 0);
        return res;
    }
    public void backtrack(int[] nums, int start, int curOr){
        if(start==nums.length) return;
        backtrack(nums, start+1, curOr);
        curOr |= nums[start];
        if(curOr>max){
            max=curOr;
            res=1;
        }
        else if(curOr==max){
            res++;
        }
        backtrack(nums, start+1, curOr);
    }
}

class Solution {
public:

    void try_make_max(int tmp_m, int i, vector<int>& nums, int max_or_sub, int& res){
        if (i >= nums.size()) return;
        tmp_m = tmp_m | nums[i];
        if (tmp_m == max_or_sub) res++;
        for (i++; i < nums.size(); i++) {
            try_make_max(tmp_m, i, nums, max_or_sub, res);
        }
    }

    int countMaxOrSubsets(vector<int>& nums) {
        int max_or_sub = 0;

        for (int num : nums) {
            max_or_sub = max_or_sub | num;
        }
        int res = 0;
        for (int i = 0; i < nums.size(); ++i){
            try_make_max(0, i, nums, max_or_sub, res);
        }
        return res;
    }
};

class Solution {
    int max_or = 0;
    int[] nums;
    public int countMaxOrSubsets(int[] nums) {
        for (int n : nums) max_or |= n;
        this.nums = nums;
        return backtrack(0, 0);
        //return backtrack(1, 0) + backtrack(1, nums[0]);
    }
    int backtrack(int index, int curr_or) {
        if (index == nums.length) {
            return curr_or == max_or ? 1 : 0;
        }
        if (curr_or == max_or) {
            return 1 << (nums.length - index);
        }
        int exclude = backtrack(index + 1, curr_or);
        int include = backtrack(index + 1, curr_or | nums[index]);
        return include + exclude;
    }
}
[/ICODE][/ISPOILER]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        r = 0
        while True:
            if n == 1:
                return '1' if r%2==1 else '0'
            if k == 1:
                return '1' if r%2==1 else '0'
            if k == 2**n-1:
                return '0' if r%2==1 else '1'
            if k == 2**(n-1):
                return '0' if r%2==1 else '1'
            if k > 2**(n-1):
                k = 2**n-k
                r+=1
            n-=1

public class Solution
{
    public char FindKthBit(int n, int k)
    {
        List<char> result = new();
        result.Add('0');
        Recursive(result, 1, n);

        return result[k - 1];
    }

    public void Recursive(List<char> currentS, int ith, int n)
    {
        if (ith == n)
        {
            return;
        }

        int from = currentS.Count - 1;
        currentS.Add('1');
        for (int i = 0; i <= from; i++)
        {
            char c = currentS[from - i];
            currentS.Add(c == '1' ? '0' : '1');
        }

        Recursive(currentS, ith + 1, n);
    }
}

class Solution {
    final char zero = '0';
    final char one = '1';
    public char findKthBit(int n, int k) {        
        if (n == 1) return zero;
        int size = (1<<n) - 1;
        int mid = (size) >> 1;
        if (k - 1== mid) return one;
        if (k - 1< mid) {
            return findKthBit(n-1, k);
        }
        return one == findKthBit(n-1 , size - k + 1) ? zero : one;
    }
}
[CODE]
[SPOILER]

[ATTACH type="full"]2741634[/ATTACH][ATTACH type="full"]2741634[/ATTACH]