Find Sum of Array Product of Magical Sequences - Problem

Array Math Dynamic Programming Bit Manipulation Combinatorics Bitmask Hard

You are given two integers m and k, and an integer array nums.

A sequence of integers seq is called magical if:

seq has a size of m
0 <= seq[i] < nums.length
The binary representation of 2^seq[0] + 2^seq[1] + ... + 2^seq[m-1] has k set bits

The array product of this sequence is defined as prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[m-1]]).

Return the sum of the array products for all valid magical sequences. Since the answer may be large, return it modulo 10^9 + 7.

A set bit refers to a bit in the binary representation of a number that has a value of 1.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,1], m = 2, k = 2

› Output: 22

💡 Note: Valid magical sequences: [0,0] (2^0+2^0=2, 1 set bit, but k=2 so invalid), [0,1] (2^0+2^1=3, 2 set bits, product=2*3=6), [0,2] (2^0+2^2=5, 2 set bits, product=2*1=2), [1,0] (2^1+2^0=3, 2 set bits, product=3*2=6), [1,2] (2^1+2^2=6, 2 set bits, product=3*1=3), [2,0] (2^2+2^0=5, 2 set bits, product=1*2=2), [2,1] (2^2+2^1=6, 2 set bits, product=1*3=3). Sum = 6+2+6+3+2+3 = 22.

Example 2 — Single Element

$ Input: nums = [5], m = 1, k = 1

› Output: 5

💡 Note: Only sequence [0] is valid: 2^0=1 has 1 set bit, product=5.

Example 3 — No Valid Sequences

$ Input: nums = [1,2], m = 2, k = 1

› Output: 5

💡 Note: Possible sequences of length 2: [0,0] (2^0+2^0=2, 1 set bit, product=1*1=1), [0,1] (2^0+2^1=3, 2 set bits), [1,0] (2^1+2^0=3, 2 set bits), [1,1] (2^1+2^1=4, 1 set bit, product=2*2=4). Valid sequences with k=1 set bits: [0,0] and [1,1]. Sum = 1+4 = 5.

Constraints

1 ≤ nums.length ≤ 20
1 ≤ nums[i] ≤ 10⁹
1 ≤ m ≤ nums.length
1 ≤ k ≤ m

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 18 f Meta 15 a Amazon 12

This problem requires finding all magical sequences of length m where the sum of powers of 2 has exactly k set bits. The key insight is using dynamic programming to track sequences by length and set bit count. The optimal approach uses DP with state dp[length][setBits] and processes each array element to build valid sequences. Time: O(n×m×k), Space: O(m×k).

Common Approaches

✓ Greedy

⏱️ Time: N/A Space: N/A

Brute Force Enumeration

⏱️ Time: O(n^m × m) Space: O(m)

For each possible sequence of m indices from the array, calculate the sum of powers of 2 and check if it has exactly k set bits. If valid, multiply the corresponding array elements and add to result.

Dynamic Programming with Memoization

⏱️ Time: O(n × m × 2^n) Space: O(n × m × 2^n)

Instead of generating all sequences, we use dynamic programming to count combinations. We track the current position, remaining slots to fill, and current bitmask, memoizing results to avoid redundant calculations.

Optimized DP with Bit Manipulation

⏱️ Time: O(n × m × k) Space: O(m × k)

This approach uses a more efficient DP formulation where we iterate through each array element and decide whether to include it. We use bit manipulation tricks to efficiently check set bits and manage the bitmask.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;

int countSetBits(long long n) {
    int count = 0;
    while (n > 0) {
        if (n & 1) count++;
        n >>= 1;
    }
    return count;
}

void generateSequences(int* nums, int* seq, int pos, int n, int m, int k, long long* total_sum) {
    if (pos == m) {
        // Calculate 2^seq[0] + 2^seq[1] + ... + 2^seq[m-1]
        long long power_sum = 0;
        for (int i = 0; i < m; i++) {
            power_sum += (1LL << seq[i]);
        }
        
        // Count set bits in power_sum
        int set_bits = countSetBits(power_sum);
        
        // Check if it has exactly k set bits
        if (set_bits == k) {
            // Calculate array product
            long long product_val = 1;
            for (int i = 0; i < m; i++) {
                product_val = (product_val * nums[seq[i]]) % MOD;
            }
            *total_sum = (*total_sum + product_val) % MOD;
        }
        return;
    }
    
    for (int i = 0; i < n; i++) {
        seq[pos] = i;
        generateSequences(nums, seq, pos + 1, n, m, k, total_sum);
    }
}

int solution(int* nums, int n, int m, int k) {
    long long total_sum = 0;
    int* seq = malloc(m * sizeof(int));
    
    generateSequences(nums, seq, 0, n, m, k, &total_sum);
    
    free(seq);
    return (int)total_sum;
}

int main() {
    char nums_str[1000];
    int m, k;
    
    fgets(nums_str, sizeof(nums_str), stdin);
    scanf("%d", &m);
    scanf("%d", &k);
    
    // Parse nums array
    int nums[100];
    int n = 0;
    
    // Remove brackets and parse
    char* ptr = nums_str;
    while (*ptr) {
        if (*ptr >= '0' && *ptr <= '9') {
            nums[n] = 0;
            while (*ptr >= '0' && *ptr <= '9') {
                nums[n] = nums[n] * 10 + (*ptr - '0');
                ptr++;
            }
            n++;
        } else if (*ptr == '-') {
            ptr++;
            nums[n] = 0;
            while (*ptr >= '0' && *ptr <= '9') {
                nums[n] = nums[n] * 10 + (*ptr - '0');
                ptr++;
            }
            nums[n] = -nums[n];
            n++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(nums, n, m, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen