Problem

Alice and Bob are opponents in an archery competition. The competition has set the following rules:

  1. Alice first shoots numArrows arrows and then Bob shoots numArrows arrows.
  2. The points are then calculated as follows: 1. The target has integer scoring sections ranging from 0 to 11 inclusive. 2. For each section of the target with score k (in between 0 to 11), say Alice and Bob have shot ak and bk arrows on that section respectively. If ak >= bk, then Alice takes k points. If ak < bk, then Bob takes k points. 3. However, if ak == bk == 0, then nobody takes k points.
  • For example, if Alice and Bob both shot 2 arrows on the section with score 11, then Alice takes 11 points. On the other hand, if Alice shot 0 arrows on the section with score 11 and Bob shot 2 arrows on that same section, then Bob takes 11 points.

You are given the integer numArrows and an integer array aliceArrows of size 12, which represents the number of arrows Alice shot on each scoring section from 0 to 11. Now, Bob wants to maximize the total number of points he can obtain.

Return the arraybobArrows _which represents the number of arrows Bob shot oneach scoring section from _0 to11. The sum of the values in bobArrows should equal numArrows.

If there are multiple ways for Bob to earn the maximum total points, return any one of them.

Examples

Example 1

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2022/02/24/ex1.jpg)

Input: numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
Output: [0,0,0,0,1,1,0,0,1,2,3,1]
Explanation: The table above shows how the competition is scored. 
Bob earns a total point of 4 + 5 + 8 + 9 + 10 + 11 = 47.
It can be shown that Bob cannot obtain a score higher than 47 points.

Example 2

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2022/02/24/ex2new.jpg)

Input: numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
Output: [0,0,0,0,0,0,0,0,1,1,1,0]
Explanation: The table above shows how the competition is scored.
Bob earns a total point of 8 + 9 + 10 = 27.
It can be shown that Bob cannot obtain a score higher than 27 points.

Constraints

  • 1 <= numArrows <= 10^5
  • aliceArrows.length == bobArrows.length == 12
  • 0 <= aliceArrows[i], bobArrows[i] <= numArrows
  • sum(aliceArrows[i]) == numArrows

Solution

Method 1 – Bitmask Enumeration

Intuition

We want to maximize Bob’s score by choosing which sections to beat Alice in. For each section, Bob must shoot more arrows than Alice to win that section’s points. Since there are only 12 sections, we can try all possible combinations (subsets) of sections Bob can win, and pick the one that gives the highest score without exceeding his total arrows.

Approach

  1. For each subset of the 12 sections (using bitmask from 1 to 2^12-1):
    • For each section in the subset, calculate the minimum arrows needed to beat Alice (aliceArrows[i] + 1).
    • Sum the arrows needed for the subset.
    • If the total arrows used is less than or equal to numArrows, calculate the score (sum of section indices in the subset).
    • Track the subset with the highest score.
  2. For the best subset, assign arrows as calculated, and put any leftover arrows in section 0.
  3. Return the array representing Bob’s arrow distribution.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
        int maxScore = 0, mask = 0;
        for (int s = 1; s < (1 << 12); ++s) {
            int arrows = 0, score = 0;
            for (int i = 0; i < 12; ++i) {
                if (s & (1 << i)) {
                    arrows += aliceArrows[i] + 1;
                    score += i;
                }
            }
            if (arrows > numArrows) continue;
            if (score > maxScore) {
                maxScore = score;
                mask = s;
            }
        }
        vector<int> ans(12);
        int arrows = numArrows;
        for (int i = 0; i < 12; ++i) {
            if (mask & (1 << i)) {
                ans[i] = aliceArrows[i] + 1;
                arrows -= ans[i];
            }
        }
        ans[0] += arrows;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func maximumBobPoints(numArrows int, aliceArrows []int) []int {
    maxScore, mask := 0, 0
    for s := 1; s < (1 << 12); s++ {
        arrows, score := 0, 0
        for i := 0; i < 12; i++ {
            if s&(1<<i) != 0 {
                arrows += aliceArrows[i] + 1
                score += i
            }
        }
        if arrows > numArrows {
            continue
        }
        if score > maxScore {
            maxScore = score
            mask = s
        }
    }
    ans := make([]int, 12)
    arrows := numArrows
    for i := 0; i < 12; i++ {
        if mask&(1<<i) != 0 {
            ans[i] = aliceArrows[i] + 1
            arrows -= ans[i]
        }
    }
    ans[0] += arrows
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        int maxScore = 0, mask = 0;
        for (int s = 1; s < (1 << 12); ++s) {
            int arrows = 0, score = 0;
            for (int i = 0; i < 12; ++i) {
                if ((s & (1 << i)) != 0) {
                    arrows += aliceArrows[i] + 1;
                    score += i;
                }
            }
            if (arrows > numArrows) continue;
            if (score > maxScore) {
                maxScore = score;
                mask = s;
            }
        }
        int[] ans = new int[12];
        int arrows = numArrows;
        for (int i = 0; i < 12; ++i) {
            if ((mask & (1 << i)) != 0) {
                ans[i] = aliceArrows[i] + 1;
                arrows -= ans[i];
            }
        }
        ans[0] += arrows;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    fun maximumBobPoints(numArrows: Int, aliceArrows: IntArray): IntArray {
        var maxScore = 0
        var mask = 0
        for (s in 1 until (1 shl 12)) {
            var arrows = 0
            var score = 0
            for (i in 0 until 12) {
                if ((s and (1 shl i)) != 0) {
                    arrows += aliceArrows[i] + 1
                    score += i
                }
            }
            if (arrows > numArrows) continue
            if (score > maxScore) {
                maxScore = score
                mask = s
            }
        }
        val ans = IntArray(12)
        var arrows = numArrows
        for (i in 0 until 12) {
            if ((mask and (1 shl i)) != 0) {
                ans[i] = aliceArrows[i] + 1
                arrows -= ans[i]
            }
        }
        ans[0] += arrows
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: list[int]) -> list[int]:
        max_score = 0
        mask = 0
        for s in range(1, 1 << 12):
            arrows = 0
            score = 0
            for i in range(12):
                if s & (1 << i):
                    arrows += aliceArrows[i] + 1
                    score += i
            if arrows > numArrows:
                continue
            if score > max_score:
                max_score = score
                mask = s
        ans = [0] * 12
        arrows = numArrows
        for i in range(12):
            if mask & (1 << i):
                ans[i] = aliceArrows[i] + 1
                arrows -= ans[i]
        ans[0] += arrows
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn maximum_bob_points(num_arrows: i32, alice_arrows: Vec<i32>) -> Vec<i32> {
        let mut max_score = 0;
        let mut mask = 0;
        for s in 1..(1 << 12) {
            let mut arrows = 0;
            let mut score = 0;
            for i in 0..12 {
                if (s & (1 << i)) != 0 {
                    arrows += alice_arrows[i] + 1;
                    score += i as i32;
                }
            }
            if arrows > num_arrows {
                continue;
            }
            if score > max_score {
                max_score = score;
                mask = s;
            }
        }
        let mut ans = vec![0; 12];
        let mut arrows = num_arrows;
        for i in 0..12 {
            if (mask & (1 << i)) != 0 {
                ans[i] = alice_arrows[i] + 1;
                arrows -= ans[i];
            }
        }
        ans[0] += arrows;
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    maximumBobPoints(numArrows: number, aliceArrows: number[]): number[] {
        let maxScore = 0, mask = 0;
        for (let s = 1; s < (1 << 12); ++s) {
            let arrows = 0, score = 0;
            for (let i = 0; i < 12; ++i) {
                if (s & (1 << i)) {
                    arrows += aliceArrows[i] + 1;
                    score += i;
                }
            }
            if (arrows > numArrows) continue;
            if (score > maxScore) {
                maxScore = score;
                mask = s;
            }
        }
        const ans = new Array(12).fill(0);
        let arrows = numArrows;
        for (let i = 0; i < 12; ++i) {
            if (mask & (1 << i)) {
                ans[i] = aliceArrows[i] + 1;
                arrows -= ans[i];
            }
        }
        ans[0] += arrows;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(2^12 * 12); we enumerate all subsets (2^12) and for each, check all 12 sections.
  • 🧺 Space complexity: O(1); only a few variables and the answer array of size 12 are used.