Loading page…
Practice problem · easy
The admin console of an app stores each user's permissions as one whole number, a mask. Each bit that is 1 in the mask is one permission the user has. A mask of 5 is 101 in binary, so it grants two permissions.
The security team wants the list of masks ordered from the fewest permissions to the most. Masks with the same number of permissions go in ascending order of the mask.
Write sort_by_permissions(masks).
masks[i] is a whole number from 0 up. The number of permissions is the number of 1 bits in its binary form.Input: masks = [5, 3, 8, 7, 1, 6]
Output: [1, 8, 3, 5, 6, 7]Give each mask a two-part key: its number of 1 bits, then its value.
| Mask | Binary | 1 bits | Key |
|---|---|---|---|
| 5 | 101 | 2 | (2, 5) |
| 3 | 011 | 2 | (2, 3) |
| 8 | 1000 | 1 | (1, 8) |
| 7 | 111 | 3 | (3, 7) |
| 1 | 001 | 1 | (1, 1) |
| 6 | 110 | 2 | (2, 6) |
Sorted by key: (1, 1), (1, 8), (2, 3), (2, 5), (2, 6), (3, 7).
Input: masks = [5, 3, 2, 1]
Output: [1, 2, 3, 5]The masks 1 and 2 have one bit each, and 3 and 5 have two bits each. Inside each pair, the smaller mask goes first.
Input: masks = [3, 4]
Output: [4, 3]4 is 100, one permission. 3 is 011, two permissions. So 4 comes first, even though 3 is smaller.
0 ≤ masks.length ≤ 100,000 (users)0 ≤ masks[i] ≤ 1,000,000,000, so every mask fits in 30 bits.Sorting by hand with nested loops costs about n × n / 4 steps on average, which is 2.5 × 10^9 at n = 100,000. A library sort costs n log n comparisons. Counting the bits of a mask takes at most 30 steps.
sort_by_permissions · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.