Assign Elements to Groups with Constraints

Assign Elements to Groups with Constraints - Problem

You are given an integer array groups, where groups[i] represents the size of the i-th group. You are also given an integer array elements.

Your task is to assign one element to each group based on the following rules:

An element at index j can be assigned to a group i if groups[i] is divisible by elements[j].
If there are multiple elements that can be assigned, assign the element with the smallest index j.
If no element satisfies the condition for a group, assign -1 to that group.

Return an integer array assigned, where assigned[i] is the index of the element chosen for group i, or -1 if no suitable element exists.

Note: An element may be assigned to more than one group.

Input & Output

Example 1 — Basic Assignment

$ Input: groups = [12, 8, 15], elements = [2, 3, 4, 5]

› Output: [0, 0, 1]

💡 Note: Group 0 (size 12): 12 % 2 = 0, so assign element at index 0. Group 1 (size 8): 8 % 2 = 0, so assign element at index 0. Group 2 (size 15): 15 % 2 ≠ 0, but 15 % 3 = 0, so assign element at index 1.

Example 2 — No Valid Assignment

$ Input: groups = [7, 11], elements = [2, 4, 6]

› Output: [-1, -1]

💡 Note: Group 0 (size 7): 7 % 2 ≠ 0, 7 % 4 ≠ 0, 7 % 6 ≠ 0, so assign -1. Group 1 (size 11): 11 % 2 ≠ 0, 11 % 4 ≠ 0, 11 % 6 ≠ 0, so assign -1.

Example 3 — Same Element for Multiple Groups

$ Input: groups = [6, 12, 18], elements = [3, 9]

› Output: [0, 0, 0]

💡 Note: All groups are divisible by element 3 (at index 0): 6 % 3 = 0, 12 % 3 = 0, 18 % 3 = 0. Since we pick the smallest index, all groups get assigned element at index 0.

Constraints

1 ≤ groups.length, elements.length ≤ 10³
1 ≤ groups[i] ≤ 10⁹
0 ≤ elements[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Groups array with sizes and elements array with values

Process

For each group, find first element that divides the group size

Output

Array of element indices or -1 for each group

Key Takeaway

🎯 Key Insight: Always assign the first (smallest index) element that satisfies the divisibility constraint for each group

Asked in

G Google 15 a Amazon 12 M Microsoft 8 Apple 6

The problem requires assigning elements to groups based on divisibility constraints. The key insight is to always choose the element with the smallest index that satisfies the divisibility condition. The optimal approach iterates through each group and checks elements in order until finding the first valid assignment. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Early Termination	O(n×m)	O(1)	Same approach as brute force but with optimizations like skipping zero elements and early termination
Brute Force - Check All Elements	O(n×m)	O(1)	For each group, iterate through all elements to find the first valid assignment

Optimized - Early Termination — Algorithm Steps

Skip elements that are zero (division by zero)
For each group, check elements in order
Break immediately when first valid element is found
Continue to next group

Visualization

Tap to expand

Step-by-Step Walkthrough

Skip Zeros

Avoid division by zero errors

Early Break

Stop at first valid element

Result

Efficient assignment with fewer checks

Code -

solution.c — C

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

int* solution(int* groups, int groupsSize, int* elements, int elementsSize, int* returnSize) {
    int* result = (int*)malloc(groupsSize * sizeof(int));
    *returnSize = groupsSize;
    
    for (int i = 0; i < groupsSize; i++) {
        result[i] = -1;
        for (int j = 0; j < elementsSize; j++) {
            // Skip zero elements to avoid division by zero
            if (elements[j] == 0) continue;
            if (groups[i] % elements[j] == 0) {
                result[i] = j;
                break; // Early termination - first valid element
            }
        }
    }
    return result;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing - assumes format [1,2,3]
    int groups[100], elements[100];
    int groupsSize = 0, elementsSize = 0;
    
    // Parse groups
    char* token = strtok(line1 + 1, ",]");
    while (token) {
        groups[groupsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse elements
    token = strtok(line2 + 1, ",]");
    while (token) {
        elements[elementsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(groups, groupsSize, elements, elementsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Still need to check up to m elements for each of n groups in worst case

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables and result array

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

487 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

Optimized - Early Termination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler