Maximum K-Shared Feature Group
In the context of understanding user demographics and interests on a platform like LinkedIn, identifying groups of users who share very specific common attributes is crucial for targeted outreach, content recommendations, and community building. Each user's profile can be represented as a bitmask, where individual bits correspond to distinct features or interests (e.g., skills, industries, groups). This problem challenges you to find the largest possible group of users who collectively possess a precisely defined set of k common features.
Your task is to implement a function maxKSharedFeatureGroup that takes an array of non-negative integers profiles (representing user feature sets) and an integer k. The function should return the maximum possible size of a group of users such that:
M with exactly k bits set (popcount(M) == k).P in the identified group possesses all features specified by M. That is, for every user P in the group, (P & M) == M.Function Signature:
function maxKSharedFeatureGroup(profiles: number[], k: number): number
profiles: An array of non-negative integers, where each integer profiles[i] represents a unique user's feature set as a bitmask.k: An integer representing the exact number of common features required for the group's defining mask M.Return Value:
M with popcount(M) == k yields any users, or k is out of valid range for available bits), return 0.profiles are guaranteed to be unique.2^20.popcount(X) refers to the number of set bits (1s) in the binary representation of X.Examples
Example 1
Input:
profiles = [3, 5, 6], k = 1
Output:
2
Note:
Profiles in binary: 3 (011_2), 5 (101_2), 6 (110_2). k = 1.
We need to find a common mask M with popcount(M) == 1 that maximizes group size.
M = 1 (001_2): Users 3 (011) and 5 (101) both have bit 0 set. Group: {3, 5}. Size: 2.M = 2 (010_2): Users 3 (011) and 6 (110) both have bit 1 set. Group: {3, 6}. Size: 2.M = 4 (100_2): Users 5 (101) and 6 (110) both have bit 2 set. Group: {5, 6}. Size: 2.
The maximum group size is 2.Example 2
Input:
profiles = [7, 15, 11], k = 2
Output:
3
Note:
Profiles in binary: 7 (0111_2), 15 (1111_2), 11 (1011_2). k = 2.
We need a common mask M with popcount(M) == 2.
Consider M = 3 (0011_2) (bits 0 and 1 set, popcount=2):
7 (0111) has bits 0 and 1 set. (7 & 3) == 3. Yes.15 (1111) has bits 0 and 1 set. (15 & 3) == 3. Yes.11 (1011) has bits 0 and 1 set. (11 & 3) == 3. Yes.
Thus, for M=3, the group {7, 15, 11} of size 3 is valid.
There are other masks with popcount=2 (e.g., M=5, M=6), but none yield a larger group. The maximum group size is 3.Example 3
Input:
profiles = [1, 2, 4, 8], k = 2
Output:
0
Note:
Profiles in binary: 1 (0001_2), 2 (0010_2), 4 (0100_2), 8 (1000_2). k = 2.
Each profile has exactly one bit set (popcount=1). To form a group, we need a common mask M with popcount(M) == 2. If M has two bits set (e.g., M=3 (0011_2)), no profile in the input profiles can be a superset of M, because each profile only has one bit set. Thus, no group can be formed, and the maximum size is 0.
Constraints
1 <= profiles.length <= 10^50 <= profiles[i] < 2^20 (i.e., profiles fit within 20 bits)0 <= k <= 20profiles[i] values are unique.k=0, or k being larger than any possible popcount.Loading editor...