Find Products of Elements of Big Array - Practice Coding Problems

Find Products of Elements of Big Array - Problem

Find Products of Elements of Big Array

Imagine a magical array called big_nums that's constructed in a fascinating way! For every positive integer, we create its powerful array - which contains all the powers of 2 that sum up to that number (based on its binary representation).

For example:
• Number 13 has binary 1101, so its powerful array is [1, 4, 8] (positions of 1-bits)
• Number 23 has binary 10111, so its powerful array is [1, 2, 4, 16]

The big_nums array is formed by concatenating all these powerful arrays in order:
[1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]

Your task: Given multiple queries [from, to, mod], calculate the product of elements from index from to to (inclusive) in big_nums, modulo mod.

Can you solve this efficiently without actually building the massive array?

Input & Output

example_1.py — Basic Query

$ Input: queries = [[0, 2, 3]]

› Output: [2]

💡 Note: big_nums = [1, 2, 1, 2, 4, ...]. Range [0,2] contains [1,2,1]. Product = 1×2×1 = 2. Since 2 < 3, result is 2.

example_2.py — Multiple Queries

$ Input: queries = [[2, 5, 4], [0, 2, 3]]

› Output: [0, 2]

💡 Note: Range [2,5] = [1,2,4,1] → product = 8 ≡ 0 (mod 4). Range [0,2] = [1,2,1] → product = 2.

example_3.py — Large Numbers

$ Input: queries = [[10, 15, 7]]

› Output: [1]

💡 Note: For large ranges, we need efficient calculation without building the actual array. The product modulo 7 equals 1.

Constraints

1 ≤ queries.length ≤ 500
queries[i].length == 3
0 ≤ from_i ≤ to_i ≤ 10¹⁵
2 ≤ mod_i ≤ 10⁹
The answer is guaranteed to fit in a 32-bit integer.

Visualization

Tap to expand

Understanding the Visualization

Extract Powers

Each number contributes its binary powers to the sequence

Mathematical Mapping

Use formulas to find position without building array

Efficient Calculation

Count and multiply using modular arithmetic

Key Takeaway

🎯 Key Insight: Instead of building the massive array, use mathematical formulas to count power occurrences and binary search for efficient index mapping!

Asked in

G Google 45 f Meta 32 a Amazon 28 ⊞ Microsoft 22

The optimal approach uses binary search and bit manipulation to avoid building the massive array. Key insights: (1) Use binary search to map indices to numbers, (2) Count occurrences of each power of 2 mathematically, (3) Apply modular exponentiation for efficient calculation. This achieves O(Q × log²N) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search + Bit Manipulation	O(Q * log²N)	O(1)	Use binary search to find position mapping and bit manipulation for efficient calculation
Brute Force (Build Array)	O(N + Q*R)	O(N)	Build the big_nums array explicitly and calculate products directly

Binary Search + Bit Manipulation — Algorithm Steps

Create a function to count total elements up to number n using bit manipulation
Use binary search to find which number contains a given index
For range queries, count occurrences of each power of 2 in the range
Calculate the product using modular exponentiation

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search Setup

Use cumulative count function to find position mapping

Count Powers

Count occurrences of each power of 2 in the range

Calculate Product

Use modular exponentiation for final result

Code -

solution.c — C

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

int popcount(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int countPowerInRange(int fromIdx, int toIdx, long long power) {
    int count = 0;
    int pos = 0;
    int n = 1;
    
    while (pos <= toIdx) {
        int bits = popcount(n);
        if (pos + bits - 1 >= fromIdx) {
            int powerPos = 0;
            int tempN = n;
            long long tempPower = 1;
            
            while (tempN > 0) {
                if (tempN & 1) {
                    if (pos + powerPos >= fromIdx && pos + powerPos <= toIdx && tempPower == power) {
                        count++;
                    }
                    powerPos++;
                }
                tempN >>= 1;
                tempPower <<= 1;
            }
        }
        pos += bits;
        n++;
    }
    
    return count;
}

int* findProductsOfElements(int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    *returnSize = queriesSize;
    int* results = malloc(queriesSize * sizeof(int));
    
    for (int q = 0; q < queriesSize; q++) {
        int fromIdx = queries[q][0];
        int toIdx = queries[q][1];
        int mod = queries[q][2];
        
        long long product = 1;
        long long power = 1;
        
        while (power <= 1000000000000000LL) {
            int count = countPowerInRange(fromIdx, toIdx, power);
            if (count > 0) {
                product = (product * modPow(power, count, mod)) % mod;
            }
            power <<= 1;
            if (power > toIdx) break;
        }
        
        results[q] = (int)product;
    }
    
    return results;
}

Time & Space Complexity

Time Complexity

⏱️

O(Q * log²N)

Q queries, each requiring log N binary searches and log N bit operations

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space for calculations

✓ Linear Space

42.0K Views

Medium Frequency

~35 min Avg. Time

1.5K 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search + Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler