Problem

You are given an integer array groups, where groups[i] represents the size of the ith 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.

Examples

Example 1

1
2
3
4
5
6

Input: groups = [8,4,3,2,4], elements = [4,2]
Output: [0,0,-1,1,0]
Explanation:
  * `elements[0] = 4` is assigned to groups 0, 1, and 4.
  * `elements[1] = 2` is assigned to group 3.
  * Group 2 cannot be assigned any element.

Example 2

1
2
3
4
5
6

Input: groups = [2,3,5,7], elements = [5,3,3]
Output: [-1,1,0,-1]
Explanation:
  * `elements[1] = 3` is assigned to group 1.
  * `elements[0] = 5` is assigned to group 2.
  * Groups 0 and 3 cannot be assigned any element.

Example 3

1
2
3
4

Input: groups = [10,21,30,41], elements = [2,1]
Output: [0,1,0,1]
Explanation:
`elements[0] = 2` is assigned to the groups with even values, and `elements[1] = 1` is assigned to the groups with odd values.

Constraints

  • 1 <= groups.length <= 10^5
  • 1 <= elements.length <= 10^5
  • 1 <= groups[i] <= 10^5
  • 1 <= elements[i] <= 10^5

Solution

Method 1 – Brute Force with Early Exit

Intuition

For each group, we want to find the first element (smallest index) that divides the group size. If no such element exists, we assign -1. This can be done by checking each element for each group.

Approach

  1. For each group i:
    • Iterate through all elements j in order.
    • If groups[i] % elements[j] == 0, assign j to group i and break.
    • If no such j is found, assign -1 to group i.
  2. Return the result array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        vector<int> ans(groups.size(), -1);
        for (int i = 0; i < groups.size(); ++i) {
            for (int j = 0; j < elements.size(); ++j) {
                if (groups[i] % elements[j] == 0) {
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

type Solution struct{}

func (Solution) AssignElements(groups []int, elements []int) []int {
    ans := make([]int, len(groups))
    for i := range groups {
        ans[i] = -1
        for j, e := range elements {
            if groups[i]%e == 0 {
                ans[i] = j
                break
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int[] assignElements(int[] groups, int[] elements) {
        int[] ans = new int[groups.length];
        for (int i = 0; i < groups.length; i++) {
            ans[i] = -1;
            for (int j = 0; j < elements.length; j++) {
                if (groups[i] % elements[j] == 0) {
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun assignElements(groups: IntArray, elements: IntArray): IntArray {
        val ans = IntArray(groups.size) { -1 }
        for (i in groups.indices) {
            for (j in elements.indices) {
                if (groups[i] % elements[j] == 0) {
                    ans[i] = j
                    break
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from typing import List
class Solution:
    def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
        ans: list[int] = [-1] * len(groups)
        for i, g in enumerate(groups):
            for j, e in enumerate(elements):
                if g % e == 0:
                    ans[i] = j
                    break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn assign_elements(groups: Vec<i32>, elements: Vec<i32>) -> Vec<i32> {
        let mut ans = vec![-1; groups.len()];
        for (i, &g) in groups.iter().enumerate() {
            for (j, &e) in elements.iter().enumerate() {
                if g % e == 0 {
                    ans[i] = j as i32;
                    break;
                }
            }
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(N * M), where N = groups.length and M = elements.length.
  • 🧺 Space complexity: O(N) for the answer array.