Maximum AND Sum of Array

// Accepted solution for LeetCode #2172: Maximum AND Sum of Array
class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int n = nums.length;
        int m = numSlots << 1;
        int[] f = new int[1 << m];
        int ans = 0;
        for (int i = 0; i < 1 << m; ++i) {
            int cnt = Integer.bitCount(i);
            if (cnt > n) {
                continue;
            }
            for (int j = 0; j < m; ++j) {
                if ((i >> j & 1) == 1) {
                    f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
                }
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

// Accepted solution for LeetCode #2172: Maximum AND Sum of Array
func maximumANDSum(nums []int, numSlots int) int {
	n := len(nums)
	m := numSlots << 1
	f := make([]int, 1<<m)
	for i := range f {
		cnt := bits.OnesCount(uint(i))
		if cnt > n {
			continue
		}
		for j := 0; j < m; j++ {
			if i>>j&1 == 1 {
				f[i] = max(f[i], f[i^(1<<j)]+(nums[cnt-1]&(j/2+1)))
			}
		}
	}
	return slices.Max(f)
}

# Accepted solution for LeetCode #2172: Maximum AND Sum of Array
class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)
        m = numSlots << 1
        f = [0] * (1 << m)
        for i in range(1 << m):
            cnt = i.bit_count()
            if cnt > n:
                continue
            for j in range(m):
                if i >> j & 1:
                    f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1)))
        return max(f)

// Accepted solution for LeetCode #2172: Maximum AND Sum of Array
/**
 * [2172] Maximum AND Sum of Array
 *
 * You are given an integer array nums of length n and an integer numSlots such that 2 * numSlots >= n. There are numSlots slots numbered from 1 to numSlots.
 * You have to place all n integers into the slots such that each slot contains at most two numbers. The AND sum of a given placement is the sum of the bitwise AND of every number with its respective slot number.
 *
 * 	For example, the AND sum of placing the numbers [1, 3] into slot <u>1</u> and [4, 6] into slot <u>2</u> is equal to (1 AND <u>1</u>) + (3 AND <u>1</u>) + (4 AND <u>2</u>) + (6 AND <u>2</u>) = 1 + 1 + 0 + 2 = 4.
 *
 * Return the maximum possible AND sum of nums given numSlots slots.
 *  
 * Example 1:
 *
 * Input: nums = [1,2,3,4,5,6], numSlots = 3
 * Output: 9
 * Explanation: One possible placement is [1, 4] into slot <u>1</u>, [2, 6] into slot <u>2</u>, and [3, 5] into slot <u>3</u>.
 * This gives the maximum AND sum of (1 AND <u>1</u>) + (4 AND <u>1</u>) + (2 AND <u>2</u>) + (6 AND <u>2</u>) + (3 AND <u>3</u>) + (5 AND <u>3</u>) = 1 + 0 + 2 + 2 + 3 + 1 = 9.
 *
 * Example 2:
 *
 * Input: nums = [1,3,10,4,7,1], numSlots = 9
 * Output: 24
 * Explanation: One possible placement is [1, 1] into slot <u>1</u>, [3] into slot <u>3</u>, [4] into slot <u>4</u>, [7] into slot <u>7</u>, and [10] into slot <u>9</u>.
 * This gives the maximum AND sum of (1 AND <u>1</u>) + (1 AND <u>1</u>) + (3 AND <u>3</u>) + (4 AND <u>4</u>) + (7 AND <u>7</u>) + (10 AND <u>9</u>) = 1 + 1 + 3 + 4 + 7 + 8 = 24.
 * Note that slots 2, 5, 6, and 8 are empty which is permitted.
 *
 *  
 * Constraints:
 *
 * 	n == nums.length
 * 	1 <= numSlots <= 9
 * 	1 <= n <= 2 * numSlots
 * 	1 <= nums[i] <= 15
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/maximum-and-sum-of-array/
// discuss: https://leetcode.com/problems/maximum-and-sum-of-array/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn maximum_and_sum(nums: Vec<i32>, num_slots: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2172_example_1() {
        let nums = vec![1, 2, 3, 4, 5, 6];
        let num_slots = 3;

        let result = 9;

        assert_eq!(Solution::maximum_and_sum(nums, num_slots), result);
    }

    #[test]
    #[ignore]
    fn test_2172_example_2() {
        let nums = vec![1, 3, 10, 4, 7, 1];
        let num_slots = 9;

        let result = 24;

        assert_eq!(Solution::maximum_and_sum(nums, num_slots), result);
    }
}

// Accepted solution for LeetCode #2172: Maximum AND Sum of Array
function maximumANDSum(nums: number[], numSlots: number): number {
    const n = nums.length;
    const m = numSlots << 1;
    const f: number[] = new Array(1 << m).fill(0);
    for (let i = 0; i < 1 << m; ++i) {
        const cnt = i
            .toString(2)
            .split('')
            .filter(c => c === '1').length;
        if (cnt > n) {
            continue;
        }
        for (let j = 0; j < m; ++j) {
            if (((i >> j) & 1) === 1) {
                f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & ((j >> 1) + 1)));
            }
        }
    }
    return Math.max(...f);
}