Recently, Duff has been practicing weight lifting. As a hard practice, Malek gave her a…
- User
Recently, Duff has been practicing weight lifting. As a hard practice, Malek gave her a task. He gave her a sequence of weights. Weight of i-th of them is 2wi pounds. In each step, Duff can lift some of the remaining weights and throw them away. She does this until there's no more weight left. Malek asked her to minimize the number of steps.
Duff is a competitive programming fan. That's why in each step, she can only lift and throw away a sequence of weights 2a1, ..., 2ak if and only if there exists a non-negative integer x such that 2a1 + 2a2 + ... + 2ak = 2x, i. e. the sum of those numbers is a power of two.
Duff is a competitive programming fan, but not a programmer. That's why she asked for your help. Help her minimize the number of steps. Input
The first line of input contains integer n (1 ≤ n ≤ 106), the number of weights.
The second line contains n integers w1, ..., wn separated by spaces (0 ≤ wi ≤ 106 for each 1 ≤ i ≤ n), the powers of two forming the weights values.
Output
Print the minimum number of steps in a single line.
Examples
Input
5 1 1 2 3 3
Output
2
Input
4 0 1 2 3
Output
4
Note
In the first sample case: One optimal way would be to throw away the first three in the first step and the rest in the second step. Also, it's not possible to do it in one step because their sum is not a power of two.
In the second sample case: The only optimal way is to throw away one weight in each step. It's not possible to do it in less than 4 steps because there's no subset of weights with more than one weight and sum equal to a power of two.
Assistant
We are given n up to 1e6, and each weight is a power of two: 2^{w_i}. We need to partition the multiset of weights into the smallest number of groups such that the sum of each group is a power of two. In each step we can select any subset of remaining weights (not necessarily contiguous? The problem says "a sequence of weights" but it's probably just any subset; it says "sequence" but from typical problem "Duff in Love" or something? Actually the problem statement: "In each step, Duff can lift some of the remaining weights and throw them away. She does this until there's no more weight left." And "in each step, she can only lift and throw away a sequence of weights 2a1, ..., 2ak if and only if there exists a non-negative integer x such that 2a1 + ... + 2ak = 2x, i.e., the sum of those numbers is a power of two." So it's any subset of the remaining weights, not necessarily contiguous. So it's a partition problem.
We need to minimize number of steps = number of groups in a partition of the multiset into groups, each having sum power of two.
We have n up to 1e6, weights up to 2^{10^6} huge, but we only have exponents w_i up to 10^6. So we can represent counts of each exponent. Essentially we have a multiset of numbers each being a power of 2. We need to partition into minimum number of subsets each summing to a power of 2.
This is reminiscent of problem "Duff in Love" but not exactly. There is a known Codeforces problem: "Duff in the Beach"? Actually there is "Duff and Weight Lifting" (CF # 588 (Div. 2) B?). Let me recall: The problem "Duff in Love" is about something else. I think there is a known problem: "Duff and Weight Lifting" from Codeforces Round #326 (Div. 2) B? Possibly. The problem: given w_i, you can take any subset that sums to a power of two in one move, minimize moves. Known solution: count the number of set bits when summing all numbers in binary? Or something like that.
We need to think: We have many powers of two. The sum of a group is power of two. Since each weight is itself a power of two, the sum of a set of powers of two is a power of two if and only if the binary representation of the sum has exactly one 1. This is a combinatorial condition.
One approach: This is like we want to combine weights to form powers of two. It's similar to binary addition: If we add all weights together, we get a total sum S. The binary representation of S has some number of 1's. But that's not directly the answer because we can group within. But maybe the answer equals the total number of 1's in the binary representation of the sum of all weights? Check examples:
Example1: weights: 2^1, 2^1, 2^2, 2^3, 2^3. Compute total sum: 2+2+4+8+8=24. Binary of 24: 11000 -> two 1's? Actually 24 = 16+8 => binary 11000, has two 1's? It has two 1's? 24 = 0b11000, that's two 1's (bits at positions 3 and 4? Actually 2^4=16, 2^3=8, so two ones). So answer 2 matches. Example2: weights: 1,2,4,8? Actually 2^0=1, 2^1=2, 2^2=4, 2^3=8 sum=15, binary 1111 has four 1's. Answer 4 matches. So maybe answer = number of 1's in binary representation of total sum? But is it always minimal? Let's test with a simple case: n=1, weight is any power of two, total sum = that weight, binary has one 1, answer should be 1, yes. Another: two equal weights: say 2,2 (w_i=1,1). Total sum=4, binary 100 has one 1, answer? Can we do in one step? The two weights sum to 4 which is power of two, so yes we can throw both at once, answer 1. So matches. Another: 2,4 (w_i=1,2) sum=6 binary 110 has two 1's, but can we do in one step? Sum is 6 not power of two. Two steps? Possibly we can group each individually: each is power of two, so two steps. Could we group them into one group? No because sum not power of two. Could we group into two groups but maybe one group includes both and some extra? That's all weights, not allowed. So answer 2 matches two ones. Another: three weights: 1,1,2 (w_i=0,0,1) sum=4 binary 100 (one 1). Can we do in one step? Sum=1+1+2=4, power of two, yes one step. So matches.
Consider: weights: 1,1,1,1 (four ones). Sum=4, binary 100 -> one 1. But can we do in one step? Sum of all four is 4, which is power of two, so yes one step: throw all four at once. So answer 1 matches. So seems plausible.
Consider: weights: 1,1,1 (three ones). Sum=3 binary 11 (two ones). Can we do in one step? Sum=3 not power of two. Can we do in two steps? Possibly group two ones (sum=2) and one alone (1). But 1 is power of two, so yes two steps. But also maybe group all three? No. So answer 2 matches binary ones count = 2.
Consider: weights: 1,3? Actually w_i: 2^0=1, 2^3=8? That would be 1 and 8 sum=9 binary 1001 (two ones). Can we do in two steps? Each individually works (1 and 8), so two steps. So matches.
Consider: more complex: 2,2,4,4 (w_i=1,1,2,2). Sum=12 binary 1100 (two ones). But can we do in two steps? Possibly group: (2,2,4) sum=8? Actually 2+2+4=8, power of two; and remaining 4 is power of two. So two steps. Yes matches. Another: 2,2,2,2 (four 2's). Sum=8, binary 1000 one 1, can we do in one? Sum of all is 8, power of two, yes. So matches.
Consider: 1,2,3? Actually w_i=0,1,3 -> weights 1,2,8 sum=11 binary 1011? 8+2+1=11, binary 1011 three ones. Can we do in three steps? Each individually: 1,2,8 are powers of two, so 3 steps. Could we do better? Maybe group 1+2=3 not power of two; 1+8=9; 2+8=10; all three 11. So no two-step grouping. So answer 3 matches.
Consider: 1,1,2,4 (w_i=0,0,1,2). Sum=1+1+2+4=8, binary one 1, answer 1? But can we do all in one? Sum=8, yes power of two. So 1.
Seems pattern holds.
But is it always true? Let's try a more tricky case: weights: 2,4,8,16? Sum=30, binary 11110 (four ones). Answer would be 4. But can we do in 3 steps? Possibly group (2,4,8,2?) no extra. Let's think systematically.
We need to partition multiset such that each part sums to a power of two. Equivalent to we need to cover the multiset with groups each summing to a power of two. The total sum S = sum of all weights. If we partition into k groups each summing to powers of two: say S = 2^{x1} + 2^{x2} + ... + 2^{xk}. That is a representation of S as sum of powers of two (with possible repetitions? Actually each group sum is a power of two, so S is sum of some powers of two. Not necessarily distinct. But note that the powers of two from groups can be any, not necessarily distinct. The binary representation of S is the unique representation as sum of distinct powers of two (each power appearing at most once). However, we can represent S as sum of powers of two in many ways (allowing repetitions) by "splitting" powers. For example, 8 can be represented as 8, or 4+4, or 4+2+2, etc. The minimum number of terms in such a representation where each term corresponds to a group sum? But the groups must exactly partition the multiset; the groups sums are determined by the actual composition of weights. So we cannot arbitrarily split S into powers of two; we are constrained by the available weights. The question: can we always achieve a number of groups equal to the number of ones in binary representation of S? That would be optimal because each group contributes at least one bit to S? Actually, if we have k groups, then S is sum of k powers of two. In binary, the number of ones in S is at most k, because when you add k powers of two, the number of ones in the binary sum can be less than k due to carries. But the number of ones in S is the minimum possible k? Because if we could combine groups to cause carries, the binary representation's number of ones is the minimal number of powers of two needed to represent S as a sum of powers of two (allowing repetitions)? Actually, the binary representation uses distinct powers; it's the representation with minimal number of powers of two, because any representation of S as sum of powers of two must have at least as many terms as the number of ones in its binary representation (since the binary representation is the unique representation with distinct powers; if you use multiple copies of same power, you can combine them to produce fewer terms? But if you allow repetitions, you could have more terms, but the minimum number of terms needed to sum to S is exactly the number of 1's in its binary representation (because you need at least one copy of each power that appears in binary, and you can combine them? Actually, to achieve sum S, you need at least the count of bits set, because each term is a power of two, and if you have fewer terms than bits, the maximum sum achievable with k distinct powers? Let's think: suppose S's binary has m ones. Could we represent S as sum of fewer than m powers of two (allowing repeats)? For example, S=6 (110) has two ones. Can we represent 6 as a single power? No. So minimum is 2. S=12 (1100) has two ones. Can we represent 12 as a single power? 12 is not power of two. So min 2. S=2 (10) has one one, min 1. So indeed the minimal number of powers of two that sum to S is the number of ones in its binary representation. This is a known fact: the binary representation gives the representation with the smallest number of powers of two because each power of two can be used at most once? But if repeats allowed, could we have fewer terms? For instance, S=8 (1000) has one one, min 1. S=10 (1010) has two ones; could we do with 1 term? 10 is not power of two, so min 2. So yes, the minimum number of terms needed to represent S as sum of powers of two is the number of ones in its binary representation. So any partition of the weights yields a representation of S as sum of group sums (each a power of two). Therefore the number of groups, k, must satisfy k >= number_of_ones(S). So lower bound is popcount(S). The question is: can we always achieve exactly popcount(S) groups? That would be optimal. The examples suggest yes.
Thus the problem reduces to: given a multiset of powers of two, can we partition them into exactly popcount(S) groups each summing to a power of two? And if yes, answer is popcount(S). But perhaps there are cases where it is impossible to achieve that lower bound due to constraints of the weights. Let's test with some potential counterexamples.
Consider weights: 1,1,1,1,1 (five ones). Sum=5, binary 101, popcount=2. Is it possible to partition five ones into two groups each summing to a power of two? The groups sums would need to be powers of two, and total sum=5. Possibilities: 4+1=5, both powers. So we need one group sum=4 (which would consist of four 1's) and another sum=1 (one 1). That uses exactly five 1's. So partition: four 1's together, one separate. That works. So answer 2, matches popcount.
Consider: 1,1,1,1,1,1 (six ones). Sum=6, popcount=2 (6=4+2?). Actually 6 binary 110 => popcount 2. So need groups sums 4 and 2? Or maybe 2+2+2? But two groups: sums that are powers of two and total 6. Possibilities: 4+2=6 works. So one group sum 4 (four 1's) and another sum 2 (two 1's). That works: group of four ones and group of two ones. So answer 2, popcount.
Consider: 1,1,1,1,1,1,1 (seven ones). Sum=7, popcount=3 (111). Need three groups summing to powers of two that add to 7: possibilities: 4+2+1=7. So we need groups of four ones, two ones, one one. That works.
Consider: 1,1,1,1,1,1,1,1 (eight ones). Sum=8, popcount=1, can group all eight together (sum 8). Works.
So for all ones it works.
Now consider a case where we have weights of different sizes. For example: 2,2,2 (three 2's). Sum=6 popcount=2. Need two groups summing to powers of two totalling 6. Possibilities: 4+2. Group two 2's make 4, and one 2 makes 2. So works.
Consider: 4,4,4 (three 4's). Sum=12 popcount=2. Need groups 8+4? Or 4+4+4? But we need two groups. 8+4=12. Can we get sum 8 from two 4's? Yes 4+4=8. So group two 4's ->8, and one 4->4. Works.
Consider: 2,4,6? But 6 is not a power of two weight. So all weights are powers of two. So each weight is 2^w.
Now consider a more complex multiset: say we have counts that cause some "excess" that might force more groups than popcount? Let's attempt to construct a counterexample.
We need to see if it's always possible to partition the multiset into exactly popcount(S) groups, each summing to a power of two. This is reminiscent of binary addition and carry over. It might be that we can simulate combining weights in a greedy manner: process weights from smallest to largest, combining them into powers of two (like merging two of the same size into one of the next size). That is like counting in binary. After merging all possible pairs (like we compute the total sum's binary representation), we end up with a multiset where each power of two appears at most once (i.e., the binary representation of total sum). But those "units" might not be directly the groups? Actually, if we take all weights and combine them as much as possible by repeatedly replacing two equal powers with one of the next power, we end up with a set of powers of two that are exactly the binary representation of S, each with count 0 or 1. This process corresponds to summing all weights into one number. But does that process correspond to grouping? Not exactly, because grouping is about partitioning into subsets, not merging all weights together. However, there is a known theorem: For any multiset of powers of two, the minimum number of groups such that each group sums to a power of two is equal to the number of 1's in the binary representation of the sum of all numbers. Why? Because we can always achieve that by a certain grouping: take the binary representation and "extract" groups that correspond to carrying.
I recall a Codeforces problem: "Duff in Love" is something else. The problem "Duff and Weight Lifting" (maybe problem 588A? Actually 588A is about meat). There is "Duff in the Beach". But I think I've seen this exact problem: It's Codeforces Round #326 (Div. 2) problem B? Possibly problem "Duff and Weight Lifting"? Wait, let me search memory: There is a problem "Duff and Weight Lifting" from Codeforces Round #588 (Div. 2) B? No.
I recall a problem: "Duff in Love" is about largest squarefree divisor. Another: "Duff and Meat" is about buying meat. "Duff and Weight Lifting" might be about this. Actually, I recall a problem where the solution is to count the number of set bits in the sum of the weights (in base 2). Many people solved it by just summing the exponents as frequencies and then counting bits. I think the problem is "Duff and Weight Lifting" (CF 588B? Not sure). So likely the answer is simply the number of 1's in binary representation of total sum.
But careful: The total sum S can be extremely large: n up to 1e6, each wi up to 1e6, so S could be up to 1e6 * 2^{1e6} which is astronomically huge; we cannot compute S directly in standard integer types. But we can compute its binary representation using the counts of each exponent. Essentially we can simulate binary addition of many powers of two. The binary representation's popcount can be computed by adding up the contributions of each exponent as if they were numbers in base 2 with counts. This is like adding counts in binary: we have an array of counts for each power. We can simulate carrying from lower to higher bits. At the end, the number of 1's in the binary representation of S is the total number of 1's in the final representation after all carries. Since we only need the popcount, we can simulate.
Specifically, let cnt[w] = number of weights with exponent w. Then we can process from w=0 upwards, performing carry: For each w, let cnt[w] be the number of occurrences. The sum at bit w (after previous carries) contributes to binary representation: we can compute total bits = sum_{w} (cnt[w] mod 2) after carrying? Actually, the process: Starting from w=0 up to max, we can compute total = sum cnt[w] * 2^w. But we want binary representation. Since 2^w is a single bit if we had one, but with multiple copies we have carries. Equivalent to adding all numbers. So we can do: carry = 0; for each w, total = cnt[w] + carry; then the bit at position w in S is total % 2; carry = total // 2; After processing all w up to some max, we then need to process carry until it becomes zero, and each time we have a bit of 1 if carry%2==1, and carry = carry//2. The popcount is the total number of positions where the bit is 1 in the final representation. So we can compute that.
But note that n can be up to 1e6, wi up to 1e6, so the maximum exponent is 1e6. But during carries, carry can become huge because we sum many numbers, potentially up to n. But carry in the simulation is the number of "2^{w+1}" after processing position w. At each step, total = cnt[w] + carry, then we compute bit and new carry = floor(total/2). Since cnt[w] ≤ n, and carry may accumulate, but the maximum value of carry after processing all positions up to max_w is about total sum shifted, but that can be huge as well? However, we can bound the size of carry in terms of number of bits needed: after processing position w, carry is at most (previous carry + cnt[w])/2, but carry could be as large as n/2? Actually, if we have many counts at lower bits, carry can become large. For example, if we have n = 1e6 ones (2^0), then cnt[0] = 1e6. At w=0: total = 1e6 + 0 = 1e6, bit = 0 (if even?), but we need to compute properly: Actually, we should process w=0: total = cnt[0] + carry. carry initial 0. total = 1e6. Then bit = total % 2, carry = total // 2 = 500,000. So carry becomes 500k. Then w=1: total = cnt[1] (maybe 0) + 500k = 500k. bit = 500k%2, carry = 250k. w=2: total=250k, etc. So carry halves each step, staying at most 1e6. So carry can be up to n in magnitude (since total at each step is at most n plus previous carry, but previous carry is less than total from previous step; the maximum total at any step is at most n? Actually, initial cnt[0] could be n, then total = n, carry = n/2. At w=1, if cnt[1]=0, total = n/2, carry = n/4, etc. So total never exceeds n. But what if we have large counts at high exponents? Then carry from lower bits could be smaller, but if we have many at high bits, the total at that high bit might be large? For example, suppose we have n = 1e6 copies of 2^{1e6} each. Then cnt[1e6] = 1e6. At w=1e6, total = 1e6 + carry (carry from lower bits likely 0). Then carry = 500k, which is still about n/2. So carry is O(n). So overall, carry can be represented in a 64-bit integer because n ≤ 1e6, so carry ≤ 1e6? Actually, consider scenario: we have many counts at all levels, but the total sum is huge, but the carry in the simulation is the number of multiples of 2^{w+1}, which is essentially the sum of contributions from lower bits divided by 2^{w+1}. The maximum possible carry at any step is at most total sum / 2^{w+1} which could be huge if w is small? Wait, if w is small, say w=0, total = cnt[0] + carry0 (0). carry1 = floor(total/2). That could be as large as floor(n/2) if cnt[0]=n. So it's O(n). For w=1, total = cnt[1] + carry1. Since cnt[1] could be up to n, and carry1 up to n/2, total up to 1.5n, so carry2 up to 0.75n. In general, the carry after processing w is roughly total sum / 2^{w+1}. But total sum can be as large as n * 2^{max_w}. So for small w, total sum/2^{w+1} could be huge? Let's compute: total sum = sum cnt[i] * 2^i. Suppose we have all weights at max exponent M=1e6, each weight is 2^M, and we have n=1e6 of them. Then total sum = 1e6 * 2^{1e6}. That's enormous. Now consider w=0: cnt[0]=0, carry0=0, total=0, carry1=0. So for small w, if there are no low bits, carry is small. But if we have many low bits, then total sum is not as huge? Actually, if we have many low bits, the total sum is not astronomically huge; it's at most n * 2^{max_w} but also the distribution. The carry at low w is essentially the sum of contributions from bits lower than w, divided by 2^w. That sum is at most total sum, but total sum could be huge if there are high bits. However, the contributions from high bits to low w are zero because high bits are powers greater than w. When we process from low to high, we only accumulate carries from lower bits. The sum of contributions from lower bits is at most total sum of numbers that have exponent less than w. That sum can be at most n * 2^{w-1} (since each weight with exponent < w is at most 2^{w-1}). So the total from lower bits ≤ n * 2^{w-1}. Then carry after processing w-1 is floor(that sum / 2^{w}) ≤ n * 2^{w-1} / 2^{w} = n/2. So indeed, at any step, carry is at most n/2? Let's analyze carefully.
We process w = 0,1,2,... Each step: total = cnt[w] + carry (from previous). The carry that goes into next level is floor(total/2). This carry represents how many groups of 2^{w+1} we have from the sum of cnt[w] * 2^{w} and previous carry * 2^{w} (since previous carry came from lower bits and represented that many 2^{w}). Actually, the previous carry from step w-1 is an integer such that the sum of all contributions from bits < w equals carry * 2^{w} + (some remainder bit at w-1). So the total sum from bits < w is carry * 2^{w} + remainder (where remainder < 2^{w}). So indeed, the total sum of weights with exponents < w is at most (carry * 2^{w}) + (2^{w} -1). But carry is the integer we computed. To bound carry, note that the total number of weights (counts) times the maximum weight? But we need a bound that doesn't depend on huge values.
Consider that the sum of all weights with exponent < w is at most (total number of such weights) * (2^{w} -1) since each is at most 2^{w} -1? Actually, each weight with exponent i (< w) is exactly 2^i, so the maximum sum of those weights if we had many is unbounded if we have many. But we have at most n weights total, and the maximum weight is 2^{max_w}. However, if we have many weights with exponents just below w, say w=10^6, and we have many weights with exponent 10^6-1, then total sum from those could be n * 2^{10^6-1} which is huge, but that would produce a large carry? Let's simulate: Suppose we have n=1e6 weights each of exponent M-1 = 999,999. Then cnt[M-1] = 1e6. Processing from w=0 upward, until we reach w = M-1, all previous cnt are zero. At w=M-1, total = 1e6 + carry (carry from w=M-2, which is 0). So carry after w=M-1 is 500,000. So carry is O(n). At w=M, total = cnt[M] (maybe 0) + 500,000 = 500,000, carry becomes 250,000. So still O(n). So indeed, even with very large exponents, the carry never exceeds n because it's derived from counts, not from the actual magnitudes? Let's formalize: In the process, the variable "carry" is an integer that counts the number of times 2^{w+1} has been accumulated. It can be as high as the sum of all cnt[i] for i ≤ w divided by 2^{w+1-i}? But since the total number of weights is n, and each weight contributes at most 1 to the count of some high-level carry? Actually, each weight of exponent i, when represented in base 2, contributes 1 to the count at bit i. When we add many numbers, the carry is essentially the sum of the bits at each position divided by 2, but this sum can be up to n (if all numbers have the same bit set). At each step, the maximum total = cnt[w] + carry can be at most n + (n) maybe? But is there a scenario where carry becomes larger than n? Let's try extreme: suppose we have all weights at exponent 0 (value 1). Then cnt[0]=n. At w=0: total = n, carry1 = floor(n/2). That's ≤ n/2. At w=1: total = cnt[1] + carry1. cnt[1] could be up to n, so total ≤ n + n/2 = 1.5n, carry2 ≤ 0.75n. So still ≤ 1.5n. At w=2: total ≤ cnt[2] + 0.75n ≤ n + 0.75n = 1.75n, carry3 ≤ 0.875n. As w increases, the carry approaches n but never exceeds n? Actually, the maximum total at any step could be up to n + (something less than n) ≤ 2n? Let's examine worst-case: Suppose we set cnt[w] = n for all w from 0 to some large number? But we only have n weights total, so sum of cnt[w] over all w equals n. So we cannot have cnt[w] = n for many w; they must sum to n. So at any particular w, cnt[w] ≤ n. But across many w, the sum of cnt's is n, so the total cumulative sum of cnt's up to w is ≤ n. The carry from previous steps is derived from the sum of lower bits, which can be at most the total number of weights times something? Actually, the carry from step w-1 is floor((cnt[w-1] + previous_carry)/2). But this can be up to (n + something)/2. The something is at most n? Possibly, but let's try to maximize carry at some step.
We want to see if carry can exceed n. Suppose we want carry as large as possible at step w. To maximize carry, we should have as many contributions from lower bits as possible that sum to a high multiple of 2^{w}. But each weight of exponent i contributes 2^i to the total sum. The total sum of all weights is S. The carry after processing w is floor( (S mod 2^{w+1})? Actually, after processing bits up to w, the carry is floor(S / 2^{w+1}). Because S in binary, after stripping lower w+1 bits, the remaining part is S >> (w+1). So carry after step w is exactly floor(S / 2^{w+1}). Indeed, the algorithm for binary addition yields that the carry after processing bit w is the integer part of S divided by 2^{w+1}. Because after adding all numbers, we can think of S as sum of counts times powers. The algorithm's invariant: after processing bits 0..w, the sum of contributions from those bits is (carry * 2^{w+1}) + (some remainder bits 0..w). Actually, the sum of all numbers = carry * 2^{w+1} + partial_sum(0..w). So carry = floor( S / 2^{w+1} ) after processing bits 0..w? Wait, careful: At step w, we have processed bits up to w. The total sum S can be expressed as: S = (carry * 2^{w+1}) + T, where T is the integer formed by bits 0..w of S (i.e., S mod 2^{w+1}). Because the algorithm essentially builds the binary representation. So indeed, after processing bit w, carry = floor(S / 2^{w+1}). So carry can be as large as floor(S / 2^{w+1}). Now S can be as large as n * 2^{max_w}. For small w, floor(S / 2^{w+1}) could be huge if S is huge. But S is huge when there are large exponents. However, recall that we are processing from w=0 upward. For small w, S / 2^{w+1} can be huge because S contains large contributions from high bits. For example, if we have n=1 weight with exponent 1e6, then S = 2^{1e6}. Then for w=0, floor(S / 2^{1}) = 2^{1e6 - 1} which is astronomically huge, far beyond 64-bit. But wait, does the algorithm compute that? Let's test: With one weight of exponent 1e6, cnt[1e6]=1, all other cnt=0. Start with carry=0. Process w=0: total = cnt[0] + carry = 0, bit0 = 0, carry remains 0. w=1: total=0, bit=0, carry=0. Continue until w=1e6: total = cnt[1e6] + carry = 1 + 0 = 1, bit = 1%2 =1, carry = 1//2 =0. So after w=1e6, carry=0. So at no point did carry become huge. That's because we processed from low to high, and carry only becomes the floor(S/2^{w+1}) after processing all bits up to w. But after processing w=0, floor(S/2^{1})? For S=2^{1e6}, floor(S/2)=2^{1e6-1}. But our algorithm gave carry=0 after w=0. Contradiction? So my earlier reasoning that carry = floor(S / 2^{w+1}) after processing w is wrong. Let's recalc.
We are adding many numbers. The algorithm for adding a set of numbers (each a power of two) by iterating over bits and using carry is not the same as adding them as a single large integer? Actually, typical binary addition of multiple numbers can be done by counting how many ones at each bit, then propagating carry. But if we add numbers like 2^{M} only, there is only a single 1 at bit M, so at lower bits, there are no ones, so carry stays 0. So floor(S/2^{w+1}) for w < M would be huge because S itself is huge, but the algorithm does not have a carry of that size; it's because we are not representing S as a single integer with a single carry; we are using the fact that each weight is a distinct number. The algorithm that processes bits sequentially and maintains a carry works for adding multiple numbers, but the carry at each step is not the quotient of S divided by 2^{w+1}; it's the number of "carry" bits generated from adding the numbers at lower bits. Since each number is a power of two, at low bits there might be no contributions, so the sum of contributions at low bits is 0, so carry is 0. So indeed, floor(S/2^{w+1}) for w<M is not given by the algorithm's carry because S has contributions from higher bits that haven't been processed yet. The algorithm's carry after processing w is the sum of contributions from bits 0..w divided by 2^{w+1}, not the total S divided by 2^{w+1}. So it's only the lower part. So we need to be careful: The total sum of numbers with exponent <= w is at most n * 2^{w} because each such number is at most 2^{w} and there are at most n of them. Actually, number of weights with exponent ≤ w can be up to n, but each such weight is at most 2^{w}. So the sum of contributions from exponents ≤ w is at most n * 2^{w}. Dividing by 2^{w+1} gives at most n/2. So indeed, the carry after processing w is at most n/2. More precisely, sum_{i≤w} cnt[i] * 2^{i} ≤ (max exponent ≤ w, so each ≤ 2^{w}) * n = n * 2^{w}. But is it tight? Actually, each weight with exponent i is exactly 2^{i}, not at most 2^{w}. So sum_{i≤w} cnt[i] * 2^{i} ≤ (sum_{i≤w} cnt[i]) * 2^{w} ≤ n * 2^{w}. So yes, that sum ≤ n * 2^{w}. Then after processing bits up to w, the algorithm's carry is floor( (sum_{i≤w} cnt[i] * 2^{i}) / 2^{w+1} ) which is ≤ (n * 2^{w}) / 2^{w+1} = n/2. So indeed, carry is at most n/2. Actually, it could be exactly n/2 if sum equals n * 2^{w} and that sum divided by 2^{w+1} = n/2. But sum = n * 2^{w} only if all weights are exactly 2^{w} (all same exponent w). But then there are n weights of exponent w, and for i<w, cnt=0. At w, total = n + carry (carry from lower bits is 0). Then total = n, carry next = floor(n/2). So carry = floor(n/2) ≤ n/2. So indeed, maximum carry is floor(n/2). So we can safely use a 64-bit integer.
Thus we can simulate the carry process with long long (since n up to 1e6, max carry about 5e5) easily. So algorithm: count frequencies of w_i up to max_w (maybe up to 1e6). But note that w_i can be up to 1e6, so array of size 1e6+something is okay (1e6+ a bit). But we need to go beyond that because when we process carries, we might generate bits beyond max_w. For example, if we have many weights at high exponents, the final binary representation may have bits beyond the max exponent due to carry overflow. E.g., n=2, both w=10^6, sum = 2 * 2^{1e6} = 2^{1e6+1}. So the highest bit becomes 1e6+1. So we need to continue processing carry until it becomes zero. The final carry after processing max exponent will be floor(total/2). So we need to continue while carry > 0, each step corresponds to a new exponent. Since carry ≤ n/2 initially after max exponent, but after further steps it reduces. However, carry could be as large as n/2, but we can keep an array or just simulate while loop with an integer.
But we only need popcount, not the actual bits. So we can compute popcount during the process: For each exponent w from 0 to max_w (maybe max_w + log2(n) ), we compute total = cnt[w] + carry, set popcount += total % 2, then carry = total / 2. After processing all w up to max_w, we continue with w = max_w+1, max_w+2, ... while carry > 0: popcount += carry % 2; carry /= 2.
Thus answer is popcount.
But we must confirm that this is indeed always the minimal number of steps. As argued, lower bound is popcount(S) because each group sum is a power of two, and sum of all groups is S, so the number of groups is at least the minimum number of powers of two needed to sum to S, which is popcount(S). And we think we can always achieve exactly popcount(S). However, we need to be sure that there is no obstacle that forces more groups than popcount. Let's try to find a counterexample or prove.
Consider: We need to partition the multiset such that each part sums to a power of two. Equivalent to we want to cover the multiset with groups whose sums are powers of two. This is like we want to "merge" items to form these powers. The binary representation approach suggests that if we treat the multiset as a sum of powers, we can combine them via "carry" to get the binary representation. But does this correspond to a valid partition? Possibly we can recursively break the multiset into groups that correspond to the binary digits of S. I recall a known result: For any multiset of powers of two, the minimum number of subsets with power-of-two sum equals the number of ones in the binary representation of the total sum. The proof is constructive: Process from the highest exponent. Since each weight is a power of two, we can think of the binary representation of the total sum. Let the ones be at positions b1, b2, ..., bk. Then we need to form groups summing to 2^{b_i}. The construction: we can greedily form groups by taking some weights to make each 2^{b_i} from the highest down. Because the sum of all weights is S, and S's binary has bits set. We can consider the following algorithm: While there are weights left, start a new group, and try to build it to sum to the largest remaining power of two that is ≤ total remaining sum. But we need to ensure that we can exactly achieve each power-of-two group without leftover that cannot be grouped into powers of two.
One constructive method: Sort weights ascending. Maintain a multiset of available weights. Greedy from smallest: combine two of the same size to form a larger size (like in binary addition). This is exactly the carry process. If we simulate combining two weights of same value into one weight of double value (i.e., merging them into a group? Not exactly; merging them would reduce the number of items but we are allowed to group them together only if their sum is a power of two. Actually, if we combine two 2^i into one 2^{i+1}, that's a valid group? Wait, the sum of two equal powers is 2^{i+1}, which is a power of two. So if we take two weights of same exponent, we can group them together in one step, but then we would have removed two weights and formed a new weight? But we don't create new weight; we just remove them. However, if we consider the process of grouping, we could combine two weights into a group and remove them. But if we later want to combine that group with others, we cannot because groups are disjoint. The idea of merging two equal weights into a "super-weight" is like treating them as already grouped, but if we later want to combine that super-weight with another weight of same value to form a larger group, that would correspond to grouping more than two weights together. But note that grouping is about selecting a subset to remove in one step. So we cannot "merge" and then later combine with others in another step because they're already removed. However, we could group three or more weights together in one step if they sum to a power of two. So merging is not directly applicable.
But there is a known equivalence: The minimal number of steps equals the number of 1's in the binary representation of the sum of all wi? Wait, careful: The problem statement uses weights 2^{wi}. So we have numbers like 2^{wi}. Let's test with some tricky case: Suppose we have weights: 1,2,4,8 (as earlier) sum=15 popcount=4, answer 4. Works.
What about: 1,1,2,2,4? Sum=10? 1+1+2+2+4=10 popcount=2 (binary 1010). Can we do in 2 steps? Possible grouping: (1,1,2,4)=8? 1+1+2+4=8, and remaining 2 =2. So yes 2 steps. Works.
What about: 1,1,1,2,4? Sum=9 popcount=2 (8+1). Group: (1,1,1,2,4)=9? Not power. But we need groups sums powers: 8 and 1. Can we get a group sum 8 from some subset? 4+2+1+1=8, that uses 4,2,1,1 (two ones). Remaining is 1. So yes. So 2 steps.
What about: 1,1,1,1,2,4? Sum=10 popcount=2 (8+2). Subset sum 8: 4+2+1+1=8 uses 4,2, and two ones, leaving two ones: 1+1=2? Actually remaining would be 1+1=2, which is a power. So groups: (4,2,1,1)=8, (1,1)=2. Works.
What about: 1,1,1,1,1,2,4? Sum=11 popcount=3 (8+2+1). Subset sum 8: 4+2+1+1=8 uses 4,2, and two ones. Remaining: three ones sum=3 not a power. But maybe another grouping: 8 from 4+2+1+1? That uses two ones. Another grouping: we need groups: 8, 2, 1. So we need a subset that sums to 2 and another to 1. After removing the 8 group, we have three ones left. Can we split three ones into 2 and 1? Yes, we can: choose 2 as group of two ones, and 1 as a single one. That would be groups: (4,2,1,1) =8, (1,1)=2, (1)=1. That works. So we used three groups. But could we do in two groups? Some other partition: maybe (4,2,1,1,1)=9 not power, (1,1)=2 sum=11? Not. So minimal is 3, matches popcount.
What about: 1,1,2,3? But w_i are exponents, so weight 3 means 2^3=8? Actually w_i are exponents, so 3 means 8. So we used 1,1,2,8? That is 1,1,2,8 sum=12 popcount=2 (8+4?). Wait 1+1+2+8=12 binary 1100 popcount 2. Can we do in two groups? Need groups sum to powers that add to 12, like 8+4. Is there a subset summing to 4? We have 1,1,2 can sum to 4 (2+1+1). So groups: (8) and (1,1,2) gives sums 8 and 4. So two steps. Works.
What about a case where there is no subset that sums to a needed power? Suppose S=... Let's try to find a counterexample where popcount(S) = k but we cannot partition into k groups. Suppose S=8 (popcount 1). Obviously we can group all. So trivial.
Maybe there is a case where the binary representation suggests we need e.g., 2 groups: sums 8 and 4, but the multiset cannot be partitioned into a subset summing to 8 and another summing to 4 because of distribution. For instance, consider weights: 2,2,4,4? Actually sum=12, popcount=2. We already found grouping: (2,2,4) =8? 2+2+4=8, remaining 4=4 works. Alternative: (4,4)=8? 4+4=8, remaining 2,2 sum=4 works. So fine.
Consider: 2,2,2,8? sum=14 popcount=3 (8+4+2?). 8+4+2=14. But we have 8,2,2,2. Can we get subsets: one 8, one 4 (from 2+2), and one 2. Yes: group1: (8), group2: (2,2), group3: (2). Works.
Consider: 1,1,1,7? But 7 is not allowed because weight must be power of two. So all weights are powers of two.
It seems plausible that we can always achieve popcount(S). I suspect it's a known result from binary representation and the fact that we can always partition a multiset of powers of two into groups corresponding to the binary representation of the total sum. How to prove? Induction perhaps: For a multiset of powers of two, consider the total sum S. Let the smallest exponent present be e. If there is at least two weights with exponent e, we can combine them into a group of sum 2^{e+1}? But that would be grouping two weights together; but if we group them, we remove them from the multiset, and we then need to partition the remaining. However, if we group them, that group sum is 2^{e+1} which is a power of two. So we have reduced the problem to a smaller multiset with one less group? Actually, we are trying to minimize total groups, not necessarily to combine pairs. But maybe we can always rearrange.
Better: There is a known technique: Simulate binary addition by pairing up equal powers and "carrying" them as if they were a single larger power. However, this process effectively merges weights into larger weights if we consider that we can group them together in one step. But careful: If we take two 2^e and treat them as one 2^{e+1} for future grouping, that means we are grouping them together in a step. But if we later combine that 2^{e+1} with another 2^{e+1} to make a 2^{e+2} group, that would mean grouping four original items together in one step? Actually, if we first group two 2^e into a group sum 2^{e+1}, that's one step. Then later we might want to group that group with another group? No, because groups are disjoint and steps are separate; after a group is thrown away, they are removed. So you cannot later combine groups from different steps. So the binary carry simulation cannot be directly interpreted as grouping steps; it's more about how we can partition the multiset into groups of sums that are powers of two, not about merging sequentially.
But we can think of the following: Suppose we have the multiset, and we want to partition into groups each summing to a power of two. Consider the binary representation of S. If we can show that there exists a subset that sums to one of those powers (say the largest power, 2^{b_k}) then we can remove it and recursively partition the rest. By induction, the remaining sum S' = S - 2^{b_k} has popcount = popcount(S) - 1 (since we removed the highest set bit? Not necessarily, because S' might have more ones due to borrowing). Actually, if we remove the highest set bit from S, the lower bits remain unchanged? In binary, S has some bits. If we subtract the highest power of two (i.e., the most significant bit), we are essentially turning off that bit. So popcount(S') = popcount(S) - 1 + maybe some new ones from lower bits if there is borrowing? But subtracting a power of two that corresponds to the most significant 1 simply removes that 1, and the lower bits stay the same. Because in binary, if you have a number like 1 followed by some bits, subtracting the highest power yields exactly the lower bits. For example, S=101100 (binary), highest power is 2^5=32, subtract yields 001100, which has popcount equal to popcount(S)-1? Actually S popcount=3 (bits at 5,3,2). After subtraction, we get bits at 3,2: popcount=2 = 3-1. Yes. So popcount decreases by 1. So if we can always find a subset of weights that sums to the most significant power of two (i.e., 2^{⌊log2 S⌋}), then by induction we can achieve popcount(S) groups. So the key is to prove that from any multiset of powers of two summing to S, there is always a subset that sums to the highest power of two in S (i.e., 2^{⌊log2 S⌋}). Is this always true? Intuitively, if we sort the weights descending, and start adding from the largest until we reach or exceed that power? But we need exact equality. Since all weights are powers of two, we can try a greedy: take the largest weight. If it is less than the target, we need to add smaller weights to reach exactly the target. Since the target is a power of two, and all weights are powers of two, we can use binary representation. Actually, consider the highest set bit in S, say bit m (so 2^m ≤ S < 2^{m+1}). The total sum S has bit m set. This means that when we sum all weights, the contribution to bit m from the sum of all weights is odd. Since each weight contributes 1 to bit m if its exponent is exactly m, but also weights with exponent > m contribute to higher bits, not to bit m. We need to consider carries from lower bits. The fact that bit m is 1 in the total sum indicates that the sum of counts of weights with exponent = m, plus half the sum of counts from lower bits (with carries), yields an odd number. But can we always select a subset that sums exactly to 2^m? It seems plausible because we can use a greedy algorithm: consider weights from largest down to smallest, and maintain a current sum target. I think this is always possible. For example, consider S=12 (1100), highest bit m=3 (8). We have weights: maybe [4,4,4]? Actually sum=12, highest bit is 8. But can we pick a subset summing to 8? Yes: 4+4=8. In [2,2,2,2,4]? sum=12? Actually 2+2+2+2+4=12, highest bit 8, subset 4+2+2=8? Yes 4+2+2=8. In worst-case, suppose we have [2,2,2,2,2,2]? sum=12? That's 6*2=12, highest bit 8, but can we get 8? 2+2+2+2=8, yes. So seems always possible. Could there be a case where the highest bit is 8, but all weights are 1? Then total sum must be at least 8, but if all are 1, total sum maybe 9 (popcount 2), highest bit 8, we can pick 8 ones to sum to 8. So yes. Could there be a case where the highest bit is say 16, but we have weights like 8,8,8? That sum is 24, highest bit is 16. Can we get 16? 8+8=16, yes.
What about weights: 8,4,4,2,2? sum=20, highest bit 16. Subset for 16? 8+4+4=16, yes.
What about: 8,8,2,2? sum=20, highest bit 16, subset 8+8=16, yes.
What about: 8,4,2,2? sum=16? Actually 8+4+2+2=16, highest bit 16, subset could be all (16) but that would be the whole set, leaving nothing. That's okay; then we need 0 groups? Actually we need partition into groups; if we take all as one group, then that's one group, popcount=1. So that works.
Seems always possible. But let's try to construct a potential counterexample: Suppose we have weights: 8,2,2,2,2? sum=16? 8+2+2+2+2=16, highest bit 16. Can we get subset sum 16? All sum to 16, so yes. Or perhaps a case where the highest bit is set due to a combination of many smaller weights causing a carry, but there is no single weight of that size and no combination of smaller weights that exactly equals that highest power without using all the weights? For the highest bit to be set, the sum of weights must be at least 2^m. The existence of a subset summing exactly to 2^m is equivalent to the subset sum problem with powers of two. But since all numbers are powers of two, the set is "canonical" in that any number up to the total sum can be represented as sum of distinct powers of two? Not exactly, because we may have multiple copies of the same power. Actually, with unlimited copies of powers of two, any integer can be represented in binary, provided we have enough copies. But we are limited by the actual counts. However, to represent the target 2^m, we need to use some combination of weights that sum to exactly 2^m. Since 2^m is itself a power of two, the representation in binary is just a single 1 at bit m. So we need to choose a multiset of weights such that when added, there is no carry into higher bits and exactly one at bit m. That means we need to select weights such that for each bit i < m, the sum of selected weights with exponent i is either 0 or results in a carry that eventually yields the 1 at bit m. But we just need the total to be 2^m. One simple way: select exactly one weight of size 2^m if available. If not, we can combine two of size 2^{m-1}, etc. In general, we can greedily form 2^m by taking as many as possible of the largest weights less than 2^m, and if we exceed, we might need to adjust. But because all weights are powers of two, the greedy algorithm for representing a power of two as sum of smaller powers (like binary) works if we have enough of each smaller power. But is it possible that despite the total sum having bit m set, we don't have enough of the required smaller powers to make 2^m without using all of some smaller powers that are needed to avoid leftover? But leftover is okay because we will handle the rest separately.
The critical question: Is it always possible to find a subset that sums exactly to the highest power of two (the most significant bit of total sum)? I think yes, due to the following reasoning: Consider the binary addition process that yields S. The highest set bit m arises from the sum of contributions at bit m and carry from lower bits. This implies that the total number of weights with exponent m, plus the number of carries from bit m-1, is odd. The carry from bit m-1 is floor( (cnt[m-1] + carry from lower ) /2 ). But we can construct a subset that mimics the binary addition? Alternatively, we can use the following constructive algorithm: Process the multiset from smallest to largest, and at each step, if the count of current size is even, we can pair them arbitrarily; if odd, we keep one aside. This is akin to computing the binary representation. Actually, we can think of representing the multiset as a binary number where each count cnt[i] is the number of 2^i. The binary representation of the total sum S is obtained by writing cnt in base 2 and propagating carries. The bits of S are exactly the bits we need to form groups: each 1 in S corresponds to a group that we can form by taking certain weights. There is a known method: For each bit i, if the bit in S is 1, we create a group that will sum to 2^i. We can allocate weights to groups by simulating the subtraction of the binary representation from the counts. Specifically, we can think of starting from the highest bit down: we want to form a group of size 2^i. We can allocate weights to that group using a greedy approach: take a weight of size 2^i if available; if not, take two of size 2^{i-1}, etc. This is similar to giving change. Because the total sum has bit i set, the available resources (counts) after considering higher bits are sufficient to form 2^i. This can be proven by induction on the bits.
Let's attempt a rigorous argument: Let the multiset be represented by counts c[i] for i=0..max. Let S = Σ c[i] 2^i. Compute the binary expansion of S: let b[j] be the j-th bit (0 or 1) for j=0..L. We have that after performing carries, the following holds: Starting with carry=0, for i from 0 to L, let total = c[i] + carry; then b[i] = total mod 2; carry = total // 2. And at the end carry=0.
Now, we need to partition into groups each summing to 2^{i} for some i where b[i]=1? Actually each group can be any power of two, not necessarily distinct; but we aim to have exactly popcount groups, so we need each group to correspond to a distinct bit. But we can assign groups arbitrarily; they don't have to correspond to bits. But we can construct a partition with exactly one group for each bit where b[i]=1, each summing to 2^i.
Construction: We'll process bits from low to high? Or high to low? Idea: Use the following algorithm: For each i from 0 to L, we will form b[i] groups of size 2^i, but b[i] is 0 or 1, so at most one group per bit. Actually, popcount is number of ones, so we want exactly one group per set bit.
So we need to assign some weights to group for bit i. The group for bit i must sum to 2^i. Since 2^i is relatively small compared to higher bits, we can try to form it from the smallest weights. But we have to ensure that after assigning groups for all bits, all weights are used exactly once.
Consider we simulate the binary addition in reverse: Starting from the highest bit, we can "give change". More concretely, we can think of the process of making change for the amount S using coins of denominations 2^i, but we have a multiset of coins (the weights) that we must use exactly. Instead, we want to partition the coins into groups each of which is exactly a power of two. Equivalent to: we want to color each coin with a color corresponding to a target power such that the sum of coins of that color equals that target.
This is reminiscent of the fact that the binary representation gives the minimal number of powers needed, and since each coin is a power, we can always distribute them to achieve that minimal number. I recall a known Codeforces solution: answer = number of 1s in binary representation of sum of all 2^{w_i}. So that's the accepted solution.
Therefore, I'm confident that answer = popcount(S). So we just compute popcount(S) efficiently.
Now, about constraints: n up to 10^6, w_i up to 10^6. We need O(n + max_w) time and memory. Use an array cnt of size maybe 2e6? Because carry may produce bits up to max_w + log2(n) ~ 1e6 + 20, so ~1,000,020 is fine. But we can also use a map? No need; allocate array of size maybe 2000000 to be safe, but max_w = 1e6, and log2(n) ≤ 20, so up to 1,000,020. So we can allocate cnt as vector of size MAX = 1000000 + 50? Actually, w_i can be up to 10^6, but if we have many high weights, the carry might propagate beyond max_w. For example, if all n weights are with w_i = 10^6, then total sum = n * 2^{10^6}. The binary representation of n * 2^{10^6} is just the binary representation of n shifted left by 10^6. So the highest bit will be at position 10^6 + floor(log2 n). Since n ≤ 1e6, log2(1e6) ≈ 20, so max bit is about 1,000,020. So we need to process up to that. So we can allocate an array of size MAX = 1000000 + 20 + 5 = 1000025, or even dynamic. Also, we need to handle the case where w_i may be as large as 10^6, so array index up to maybe 2,000,000 to be safe if we use doubling? But 10^6 + log2(n) is enough. However, note that we might have w_i up to 10^6, and if n is also 1e6, the highest bit is at most 10^6 + 20. So 2e6 is an overkill but safe memory-wise: 2e6 ints is 8 MB, okay. But we can be precise: MAX = 1000000 + 20 + 2 = 1000022.
But we also might have to consider when carry creates a bit beyond that. The maximum possible bit position is max_w + floor(log2(n)). Since n <= 1e6, log2(n) <= 20. So maximum bit index <= 1,000,000 + 20 = 1,000,020. So array of size 1,000,021 is sufficient. However, note that w_i can be up to 10^6, but if we have n=1e6 and all w_i=10^6, then the total sum's binary representation length = 10^6 + ceil(log2(1e6)) roughly 10^6+20, as said. So indeed.
But what about if we have w_i up to 10^6 but n=1, then max bit = 10^6, okay.
Thus we can create an array cnt of length maybe MAX = 1000000 + 30 (like 1000030) of type int (or long long?) We'll store the counts of each exponent. Since n up to 1e6, counts fit in int.
We then simulate:
carry = 0; ans = 0; for i in 0..MAX-1: total = cnt[i] + carry; ans += total & 1; carry = total >> 1; // After loop, while carry > 0: while carry: ans += carry & 1; carry >>= 1;
Output ans.
But careful: The loop must go up to at least the maximum possible bit where we might have cnt non-zero or carry non-zero. If we allocate enough size to cover max_w + log2(n) + 1, then after that carry will be zero. So we can loop up to MAX-1 inclusive.
We need to compute MAX appropriately. Since w_i max is 1e6, and n max is 1e6, the maximum exponent in total sum is at most 1e6 + ceil(log2(1e6)) = 1e6 + 20 = 1000020. Let's compute log2(1e6) ≈ 19.93, so ceil = 20. So max_bit = 1000020. To be safe, add maybe 5 more: 1000025. So we can declare array size 1000025.
Alternatively, we can use a map or just process dynamically with a while loop until carry is zero after processing all given w_i. Simpler: after reading counts, we can set maxW = maximum w_i encountered. Then we will have a loop for i = 0 to maxW + 20 (or maxW + 25). Or we can do: while (i <= maxW || carry > 0) and increment i. That way we don't need a fixed huge array; we can use a vector that we extend as needed. But since maxW is at most 1e6, and we need a few extra, we can just allocate size maxW + 50, but if maxW is small and n huge, we still may need extra bits due to carry. For example, maxW could be 0 but n = 1e6 (all zeros), then the total sum = 1e6, binary representation of 1e6 has bits up to floor(log2(1e6)) = 19, so we need indices up to 19. So we need array up to at least maxW + log2(n). So if we allocate size maxW + 30, that's safe because maxW could be 0, then array size 30 is enough. So we can compute MAX = max_w + 30 (where max_w is the maximum exponent among inputs). Since max_w ≤ 1e6, this is okay.
But careful: what if max_w is 1e6 and we need index up to 1e6+20, which is within max_w+30. So yes.
Thus we can: after reading, compute max_w = max wi. Then create an array cnt of size max_w + 31 (or +32) initialized to 0. Then for each w, increment cnt[w].
Then carry = 0; ans = 0; for i = 0; i <= max_w + 30; i++: (since we want to cover possible carries). At each i, if i < size, total = cnt[i] + carry else total = carry; then ans += total & 1; carry = total >> 1; After the loop, if carry still > 0, continue while loop. But if we set the loop bound large enough, carry will become 0. Since max needed is max_w+ceil(log2(n)), and we add 30, it should be enough. n up to 1e6, log2(1e6) < 20, so 30 is safe.
Alternatively, we could do while(carry) after processing up to max_w, but we need to know when to stop the for loop. Simpler: after processing all indices from 0 to max_w, we continue with a while loop for carry. Because after max_w, cnt[i] are 0, so the process becomes: while carry > 0, treat each step as i, total = carry, ans += carry&1, carry >>=1. That's equivalent to just counting ones in the binary representation of carry. But note: the carry after processing max_w might be large, but its binary representation's ones count is the number of remaining bits. So we can simply after the loop for i=0..max_w, compute ans += popcount(carry). Because while loop will add those bits. So we can do:
carry = 0; ans = 0; for i = 0; i <= max_w; i++) { total = cnt[i] + carry; ans += total & 1; carry = total >> 1; } ans += __builtin_popcountll(carry); // since carry may be up to ~n/2, but if we go beyond max_w, the carry is the remaining number, but we need to continue the process: Actually, after processing up to max_w, the remaining carry is floor(S / 2^{max_w+1}). This carry may be larger than 1 and have multiple bits. But to get the correct total popcount, we need to count the bits in that carry as they would appear in higher bits. That is exactly the popcount of the carry integer itself, because the subsequent bits are just the binary representation of carry. For example, S=24 (11000), max_w might be 4? Actually weights: 1,1,2,3,3 correspond to exponents 1,1,2,3,3 so max_w=3? Actually w_i max is 3. sum=24 binary 11000 (bits at 4 and 3). So max_w=3. After processing i=0..3, what happens? Let's simulate: cnt[0]=0, cnt[1]=2, cnt[2]=1, cnt[3]=2. Start carry=0. i=0: total=0 -> ans+=0, carry=0. i=1: total=2+0=2 -> ans+=0 (2%2=0), carry=1. i=2: total=1+1=2 -> ans+=0, carry=1. i=3: total=2+1=3 -> ans+=1 (3%2=1), carry=1. Now carry=1. ans currently = 1? But actual popcount of S is 2 (bits 3 and 4). The remaining carry 1 corresponds to bit 4? Indeed, we need to process i=4: total = cnt[4] (0) + carry 1 =1 -> bit4=1. So after processing max_w, we need to continue. If we just add popcount(carry) which is 1, ans becomes 2, correct. So ans += popcount(carry) works.
But careful: In the simulation, after i=3, carry=1. The next bit (i=4) would be total = cnt[4] + carry = 0+1=1 -> bit=1, then carry becomes 0. So the bits contributed by the remaining carry correspond exactly to the bits of the carry integer when written in binary? Not exactly, because if we just take popcount(carry), we are counting the bits of carry as if they represent the bits from the current position upward without further processing? However, the process of carrying beyond max_w is exactly that: the carry value is the number that will be spread across higher bits, with each step halving it. The binary representation of carry gives the bits that would appear at positions i, i+1, i+2,... as we continue. For example, if after i=3, carry=3 (binary 11). Then i=4: total=3 -> bit=1, carry=1; i=5: total=1 -> bit=1, carry=0. So the bits contributed are the bits of the binary representation of carry, but note that the bits appear starting at the next position, and the order is LSB first as we go up. Actually, if carry = 3 (binary 11), then at i=4 we output bit = carry%2 = 1, then carry becomes 1; at i=5 we output 1. So indeed the sequence of bits produced is the binary representation of carry, read from LSB to MSB. So the total number of 1's added is exactly popcount(carry). So adding popcount(carry) is correct.
Thus we can compute answer as: ans = sum_{i=0}^{max_w} ((cnt[i] + carry) % 2) + popcount(final_carry), with carry updated accordingly.
But we must be careful: In the loop, we update carry each step. So after loop, carry may be something. Then ans += __builtin_popcountll(carry). That works.
Now, what about overflow of carry? carry is at most? After each step i ≤ max_w, carry = floor((cnt[i] + previous_carry)/2). Since cnt[i] ≤ n and previous_carry ≤? The maximum value of carry at any point (including after processing max_w) is bounded by floor( (n + something)/2 ). But could it exceed n? Let's get a tighter bound: After processing i, carry = floor( (sum_{j=0}^{i} cnt[j] * 2^{j}) / 2^{i+1} ). This is ≤ (n * 2^{i}) / 2^{i+1} = n/2. So carry ≤ n/2 ≤ 5e5. So it fits in 32-bit. Actually, careful: The sum of contributions from bits ≤ i is at most total sum of all weights? But total sum of all weights includes higher bits that are not accounted yet, so it can be larger. However, we only consider weights with exponent ≤ i. That sum is at most number of such weights * 2^{i}. The number of such weights is ≤ n. So indeed, sum_{j≤i} cnt[j] * 2^{j} ≤ n * 2^{i}. Dividing by 2^{i+1} yields ≤ n/2. So yes, carry ≤ n/2. So after processing max_w, carry = floor( (sum of all weights) / 2^{max_w+1} ) ≤ n * 2^{max_w} / 2^{max_w+1} = n/2, same bound. So carry ≤ 5e5. So popcount of carry is trivial.
Thus the answer can be computed with O(n + max_w) time and O(max_w) space.
Now, we need to confirm that answer is indeed popcount(S) and not something else. Let's double-check with some random tests.
Generate a random multiset of powers of two. Compute S, popcount. Then try to see if there's an obvious reason why we can't achieve it. But the problem is from Codeforces, and I'm pretty sure the accepted solution is exactly that. I recall a problem "Duff and Weight Lifting" (maybe problem 588A? Actually, there's "Duff and Weight Lifting" from Round #588 Div 2? Let me recall: There is "Duff in Love" (588A?), "Duff and Weight Lifting" might be 588B? Not sure. But I think I've seen editorial: The answer is the number of 1's in the binary representation of the sum of all 2^{a_i}. So I'll trust that.
But just to be thorough, let's attempt to find a counterexample. Consider a case where S=2^m (popcount=1). Then answer should be 1. Can we always group all weights into one group? That would require that the sum of all weights is a power of two. But S is a power of two by definition. So yes, group all together.
Now consider S with popcount=2. Need two groups. Could there be a situation where we cannot split into two groups each power of two? That would mean that every partition into two subsets, at least one subset sum is not a power of two. But maybe we can always find a subset that sums to the higher power of two. Is it always possible? Suppose S=2^a + 2^b with a > b. We need a subset summing to 2^a. This is equivalent to the subset sum problem: does there exist a subset of the multiset that sums to 2^a? Since total sum is 2^a + 2^b, if we can't find subset sum 2^a, then the only way to partition into two groups would be with sums other than these two powers, but then total would be something else? Could we have groups sums like 2^c and 2^d with c,d not equal to a,b but summing to S? Possibly, but the total S is fixed. If we cannot get 2^a, maybe we could get two other powers that sum to S. For example, S=8+4=12. Could we partition a multiset with total 12 into groups 8 and 4? We already saw examples. But could there be a multiset where the only possible partitions into powers of two require more than 2 groups? Let's attempt to construct: Suppose we have weights: 2,2,2,2,2,2 (six 2's). Sum=12. Possible partitions: group of four 2's sum 8, group of two 2's sum 4 -> 2 groups. Also could do three groups: three groups of 4? Actually 2+2=4, 2+2=4, 2+2=4 -> three groups of 4, but that's 3 groups. So 2 groups is possible. So that works.
What about weights: 1,1,1,1,2,2,4? sum=12? 1+1+1+1+2+2+4=12. Groups: (4,2,2,1,1?) Actually 4+2+2+1+1=10 not 8. Try to get 8: 4+2+1+1=8 (using 4,2,1,1). Remaining: 1,1,2 sum=4? 1+1+2=4 yes. So 2 groups.
What about weights: 1,1,1,1,1,1,2,4? sum=13? That's 13 popcount=3 (8+4+1). Not 2.
We need total popcount=2. So S must be sum of two powers of two. Let's attempt to find a multiset with S=8+2=10, but no subset sums to 8 or 2 individually? But if there is a subset summing to 8, then we can pair. Could there be no subset summing to 8? For the total to be 10, the weights are powers of two. The largest weight is at most 8? Could be 8,4,2,1,... If there is an 8 weight present, then that alone sums to 8, done. So the only problematic case is when there is no weight of value 8, but the sum still has bit 8 set due to combination of smaller weights. For instance, suppose we have many 4's and 2's and 1's that sum to 8 via carries. For total 10, bit 8 set means the sum of all contributions yields a carry that sets bit 8. For example, could we have weights: 4,4,2? That sums to 10? 4+4+2=10, bit 8 is set? 4+4=8, plus 2=10, binary 1010, bit 8 (value 8) is set. There is no 8 weight, but we have two 4's. Subset sum to 8? Yes: 4+4=8. So that works.
What about weights: 4,2,2,2? sum=10? 4+2+2+2=10, binary 1010, bit 8 set. Subset sum 8? 4+2+2=8? 4+2+2=8 yes. Or 2+2+2+? Actually 2+2+2=6, not 8; but 4+2+2=8 works. So ok.
What about weights: 4,2,2,1,1? sum=10? 4+2+2+1+1=10. Subset sum 8? 4+2+1+1=8 yes.
What about weights: 4,4,1,1? sum=10? 4+4+1+1=10. Subset sum 8? 4+4=8 yes.
What about weights: 2,2,2,2,2? sum=10? 2+2+2+2+2=10. Subset sum 8? 2+2+2+2=8 yes.
What about weights: 4,4,2? already did.
It seems always possible to extract the highest power as a subset. Could there be a case where the highest bit is set only because of a complex carry chain and any subset that sums to that bit would require using all the weights of a certain lower value, but those are needed for other bits? However, for the existence of a subset summing to the highest bit, we don't care about the rest. We just need at least one subset. Is it always guaranteed? I think yes, due to the following: Let m = floor(log2 S). Consider the multiset. Sort the weights descending. Initialize target = 2^m. For each weight from largest down to smallest, if weight <= target, include it in the subset and subtract from target. If at the end target == 0, we have a subset summing to 2^m. Does this greedy algorithm always succeed? This is essentially the canonical coin system (powers of two) where greedy works for making any amount, provided we have enough coins. But we have limited coins; we need to check if the greedy algorithm will succeed given the multiset and the target being the highest power. Since the target is exactly the most significant bit of the total sum, we can argue that the greedy will succeed because the total sum of all coins is at least target, and the coin system is canonical. However, there might be cases where greedy fails for certain amounts even with powers of two if we have limited coins? For powers of two, greedy is optimal for any amount if we have unlimited coins, but with limited coins, greedy might fail if we don't have enough of certain denominations? Actually, consider we have coins: 4,3? Not powers. For powers of two, the greedy algorithm always works to represent any amount not exceeding total sum, provided we have the coins, because at each step, the largest coin not exceeding remaining amount is taken. Since denominations are powers of two, this yields the binary representation. However, we might run out of a certain coin. Could that cause failure? Suppose we want to make amount 6, and we have coins: 4,2,2? Greedy: take 4, remaining 2, take 2 (we have one), success. If we have coins: 4,1,1? Greedy: take 4, remaining 2, then largest ≤2 is 1, take 1, remaining 1, take 1, success. If we have coins: 4,2? Greedy: take 4, remaining 2, take 2, success. If we have coins: 4,1? cannot make 6 because total insufficient. So as long as total sum >= target, greedy using the actual available coins might fail if we don't have the needed smaller coins after taking a large one. For example, target=8, coins: 8? obviously success. target=8, coins: 4,2,2? total=8. Greedy: take 4 (largest ≤8), remaining 4, then largest ≤4 is 4? but we have only one 4? Actually we have only one 4 (since we used it), remaining coins: 2,2. Largest ≤4 is 2, take 2, remaining 2, take 2, success, sum=4+2+2=8. Works. target=8, coins: 4,4,2? greedy: take 4 (largest, but there are two 4's; we could take a 4, remaining 4, then we can take another 4, success. If we have only one 4, and many 2's: 4,2,2,2? total=10. Greedy for 8: take 4, remaining 4, then largest ≤4 is 2? take 2, remaining 2, take 2, remaining 0? Actually after taking 4, remaining 4. We have coins: 2,2,2 (since 4 used). We take a 2, remaining 2, take a 2, remaining 0. So we used 4+2+2=8, leaving one 2. Success.
Is there a case where greedy fails? Suppose target=8, coins: 6? not a power of two. But our coins are only powers of two, so denominations are 1,2,4,8,... Greedy for any target will take the largest coin not exceeding target. If we have at least one of that coin, we take it. The remainder is less than that coin value. Since the remainder is less than the coin, and the remaining denominations are all smaller powers of two, and we have the binary representation of the remainder, we need to have enough coins to represent the remainder. However, it's possible that we don't have enough of the smaller coins to make up the remainder, even though total sum is sufficient. For example, consider making amount 6 with coins: 4,2? That works. With coins: 4,1,1? works. With coins: 4,1? total 5 insufficient. For failure, we need total sum >= target but the specific combination of coins cannot represent the target. Is it possible with powers of two? Suppose we have coins: 4,2,2? That can make 6? 4+2=6, yes. 8? 4+2+2=8, yes. 9? 8+1, but if no 8 or 1, maybe 4+2+2+? total 8, can't make 9. So inability to represent a target arises when the multiset's total sum is >= target but the coins cannot sum exactly to target. With powers of two, the condition for being able to represent a target T is that for every bit position, the number of coins of that denomination plus any carried from lower bits (like in binary addition) is sufficient to cover the binary representation of T. More formally, if we sort the coins and consider their binary representation, we can represent T iff for all i, the sum of counts of coins of value 2^i plus the number of carries from lower bits (when adding the coins) is at least the i-th bit of T. But that's essentially the condition that T can be formed as a subset sum from the multiset. This is a variant of the subset sum problem with powers of two, which is equivalent to checking if the multiset's "binary representation" (when summed) can cover T without borrowing. Actually, since all coins are powers of two, the subset sum condition is that for each bit, the number of available coins of that bit, plus any carried from lower bits (i.e., we can combine lower denominations to form higher ones), must be at least the corresponding bit in T. This is exactly the condition that T ≤ S in terms of "binary dominance"? I think with powers of two, any number up to total sum S can be represented as a sum of a subset if and only if for each bit, the cumulative availability condition holds? But is that always true? For example, consider coins: 2,2 (two 2's). Total sum=4. Can we represent 3? 3 is less than 4. But can we make 3 with 2 and 2? No, because only even sums. So not all numbers up to total sum are representable. So the condition is more restrictive. So it's possible that the target T (which is 2^m) may not be representable even though S has that bit set. But note that T is exactly the most significant bit of S. Does that guarantee that it is representable? I think yes, because the most significant bit arises from the sum, and the process of addition ensures that there is a combination of coins that yields exactly that bit, perhaps by taking all coins that contributed to that bit. Actually, the existence of a subset summing to the highest power can be proved by induction: Consider the smallest weight present, say of value 2^k. If there are at least two of them, we could combine them to form a 2^{k+1} conceptually, but that's a different operation. However, there is a known lemma: In any multiset of powers of two, there exists a subset whose sum is the highest power of two not exceeding the total sum. Proof: Let m = floor(log2 S). Consider the weights of value >= 2^m? Actually, there may be none. But suppose we take all weights of value > 2^m? None because 2^m is the maximum possible value not exceeding S, but weights could be larger than 2^m? Since S < 2^{m+1}, any weight larger than 2^m would be at least 2^{m+1}, which would already exceed S, impossible because sum of all weights is S. So all weights are ≤ 2^m. So the largest weight is at most 2^m. Now, if there is a weight exactly equal to 2^m, then that weight alone is the subset. Otherwise, all weights are ≤ 2^{m-1}. Then S < 2^{m+1} but S ≥ 2^m (by definition of m). So total sum of weights, all ≤ 2^{m-1}, is at least 2^m. This is possible only if there are at least two weights, and their sum reaches 2^m. But can we always select a subset that sums exactly to 2^m? This is not trivial. However, we can use the following argument: Since all weights are ≤ 2^{m-1}, the sum S is at least 2^m, meaning that the sum of the weights is at least twice the largest possible individual weight. This suggests we can use a greedy algorithm: sort weights descending, and try to form 2^m. Because all weights are ≤ 2^{m-1}, the sum of all weights is S. Consider the binary representation of S: it has a 1 in bit m. In the process of adding the weights (as numbers), the bit m becomes 1 due to carries from lower bits. This implies that the sum of the weights, when expressed in binary, has that bit set. It is known that for powers of two, the subset sum problem is equivalent to checking whether for each bit, the number of ones in that bit position among the chosen subset matches the target. But constructing a subset summing to 2^m can be done by processing bits from low to high: we need to select a collection of weights such that when added, they produce exactly one 1 at bit m and zeros elsewhere. This is similar to solving a system of equations with carries. There might be a constructive proof via the following algorithm: Start with an empty subset. Process weights from smallest to largest. Maintain a "need" for each bit? Actually, a simpler constructive method: Use the binary representation of S. Since S = 2^m + R, where R < 2^m. We want a subset summing to 2^m. Equivalently, we want to find a subset whose sum is exactly half of (S + (2^m - R))? Not helpful.
Alternatively, there is a known result: For any multiset of powers of two, the minimal number of groups is the number of ones in the binary representation of the total sum. This is proved by showing that one can always partition the multiset into groups corresponding to the bits of S. The constructive proof often goes like: Simulate the process of adding the weights and keep track of carries. Then, for each bit that is 1 in the final sum, we can form a group consisting of certain weights that contributed to that bit. More concretely, consider the process of binary addition: we have counts c[i] and we propagate carries. At the end, we have bits b[i]. Now, we can go backwards: For each i where b[i] = 1, we can "extract" a group of total 2^i by reversing the carry process. This is similar to the algorithm for representing a number in base 2 with limited digits. I think it's doable.
Given the problem's popularity and the examples, it's safe.
Thus the solution is indeed to compute popcount of total sum.
Now, let's consider the input size: n up to 1e6, reading using fast I/O. We'll need to store cnt array of size up to max_w+30. max_w can be up to 1e6, so array of size 1,000,030 is fine (around 4 MB if int). We'll use vector or a global array.
Implementation steps:
- Read n.
- Initialize variable maxW = 0.
- Create a vector cnt. But we don't know maxW until we read all w_i. Could first read all w_i into an array? Or we can read and update maxW and also count frequencies using a map? But using a map (unordered_map) might be slower and memory heavy for 1e6 entries. Better to first read all numbers into a list, find maxW, then allocate cnt of size maxW+1 (or maxW+30) and fill frequencies. But storing all w_i (1e6 ints) is also 4 MB, acceptable. Or we could use a frequency array sized to a fixed maximum like 1000000+30 and just assume w_i ≤ 1e6. Since constraint says 0 ≤ wi ≤ 1e6, we can directly allocate array of size MAX = 1000000 + 30 (1000030). That is simpler and avoids two passes. Memory: 1000030 integers ≈ 4 MB, fine. So we can define a global array cnt[1000050] = {0}. Then read n, loop i from 0 to n-1, read w, increment cnt[w]. Also track maxW = max(maxW, w). Then after reading, we compute answer.
But careful: w_i can be up to 10^6, so array index up to 10^6 inclusive. So we need size at least 1000001. To accommodate carry bits, we will later need indices up to maybe 1000020. So we can set array size to 2000000? Actually 1000000+50 is enough. So define const int MAX = 1000000 + 50; or 2000000 to be safe? 1000000+50 = 1000050, that's okay. But let's compute max possible bit: max_w + ceil(log2(n)) ≤ 1e6 + 20 = 1000020. So 1000050 > 1000020, safe. So we can set MAX = 1000050.
But note: w_i can be exactly 1e6, so cnt[1000000] exists. We'll have indices up to 1000000. When we loop i from 0 to maxW (which is 1e6), we will access cnt[i]. Then we also need to consider bits beyond maxW due to carry. We'll handle that separately via while loop on carry. So we don't need array beyond maxW. However, if we allocate size MAX > maxW+some, it's fine. But if we want to unify, we can loop i up to MAX-1 and treat cnt[i] as 0 for i > maxW (since array is zero-initialized). That would automatically process carries without needing a separate while. But we must ensure MAX is large enough that after processing i=MAX-1, carry becomes 0. If MAX is not large enough, we might miss bits. So we can set MAX = max_w + 31 maybe. But we can compute max_w and then loop while (i <= max_w || carry > 0) incrementing i, and for i > max_w, cnt[i] = 0. That's simple: after reading, we set i=0, carry=0, ans=0. While (i <= max_w || carry > 0) { total = (i <= max_w ? cnt[i] : 0) + carry; ans += total & 1; carry = total >> 1; i++; }. That avoids needing a fixed large array beyond max_w. That is clean and safe.
Implementation:
int n; int max_w = 0; vector cnt(1000000+1, 0); // but we may need to resize after reading? Actually we can allocate size 1000000+1 (since wi <= 1e6). We'll use that.
But if max_w is less than 1e6, we still have array up to 1e6, but that's fine. We'll use that array.
Then after reading, we set i=0, carry=0, ans=0. while (i <= max_w || carry > 0) { total = carry; if (i <= max_w) total += cnt[i]; ans += total & 1; carry = total >> 1; i++; }
But note: The condition i <= max_w or carry > 0 will cause loop to continue until carry is zero. Since max_w is at most 1e6, and after processing i = max_w, we will still have i increment, and then continue while carry>0, with cnt[i] being out of bounds if i > max_w but we still access cnt[i]? In code we must check. So we should do:
int i = 0; long long carry = 0; // since may be up to 5e5, fits in int but use long long for safety. int ans = 0; while (i <= max_w || carry > 0) { long long total = carry; if (i <= max_w) total += cnt[i]; ans += total & 1; carry = total >> 1; i++; }
But be careful: when i exceeds max_w, we don't want to access cnt[i]. So condition is correct.
Now, we need to ensure that cnt is large enough to have index up to max_w. Since we allocated cnt with size maybe max_w+1? But we don't know max_w until after reading. Options:
- We can allocate a fixed size array of, say, 1000000+10 (since wi ≤ 1e6). That's safe: cnt[1000010]. Then max_w will be ≤ 1e6, so indices up to max_w are valid. And when i > max_w, we don't access cnt[i] because we check i <= max_w. So it's fine.
Thus we can do:
const int MAXW = 1000000 + 10; int cnt[MAXW] = {0};
Then read, update max_w.
Alternatively, we can use vector and resize after reading to max_w+1, but that's more work.
I'll go with fixed size array.
Now, edge cases: n=1, w=0 => cnt[0]=1, max_w=0. Loop: i=0: total = 1+0=1, ans+=1, carry=0, i=1. Now i=1 > max_w and carry=0, loop ends. ans=1. Correct.
n=0? Not possible, n>=1.
Now, confirm with sample:
Sample1: n=5, w:1,1,2,3,3. cnt[1]=2, cnt[2]=1, cnt[3]=2. max_w=3. i=0: total=0 -> ans+=0, carry=0. i=1: total=2+0=2 -> ans+=0, carry=1. i=2: total=1+1=2 -> ans+=0, carry=1. i=3: total=2+1=3 -> ans+=1, carry=1. i=4: i>max_w, total=carry=1 -> ans+=1, carry=0. i=5: loop condition false. ans=2. OK.
Sample2: n=4, w:0,1,2,3. cnt[0]=1,cnt[1]=1,cnt[2]=1,cnt[3]=1. max_w=3. i=0: total=1 -> ans+=1, carry=0. i=1: total=1 -> ans+=1, carry=0. i=2: total=1 -> ans+=1, carry=0. i=3: total=1 -> ans+=1, carry=0. i=4: loop ends. ans=4. OK.
Thus solution works.
Now, I'd like to double-check correctness with some random tests by mental or quick reasoning. But given the reasoning and known problem, it's correct.
Now, we should also consider that the input may have w_i up to 10^6, but the array size must be at least 10^6+1. We'll set MAX = 1000000 + 50 (e.g., 1000050). Use global array or static vector.
Potential pitfalls: Use of int for total and carry might overflow if we have large n and large carry? But we argued carry ≤ n/2 ≤ 5e5. However, total = cnt[i] + carry, where cnt[i] can be up to n=1e6, carry up to 5e5, so total ≤ 1.5e6, fits in 32-bit. So we can use int. But for safety, use long long.
Now, let's think about if there is any scenario where the answer is not popcount(S). Could it be that we need to consider that groups must be thrown away in steps, and the order of removal doesn't matter. The partition is independent.
But I recall a problem "Duff and Weight Lifting" where the answer is indeed the number of ones in the sum of weights. Yes, I'm pretty sure.
Thus solution is simple.
Now, for completeness, let's see if there is any twist: The problem statement says "In each step, Duff can lift some of the remaining weights and throw them away. She does this until there's no more weight left. Malek asked her to minimize the number of steps. Duff is a competitive programming fan. That's why in each step, she can only lift and throw away a sequence of weights 2a1, ..., 2ak if and only if there exists a non-negative integer x such that 2a1 + 2a2 + ... + 2ak = 2x, i. e. the sum of those numbers is a power of two." It says "sequence of weights" but it likely means a set (order doesn't matter). So yes.
Now, one might think about whether the subset must be contiguous? The word "sequence" might imply that the chosen weights must be consecutive in the original order? Usually in problems, "sequence" might refer to the fact that they are listed, but not necessarily contiguous. However, in many combinatorial problems, "sequence of weights" just means a multiset (list) of weights, not necessarily contiguous. But the problem statement: "In each step, Duff can lift some of the remaining weights and throw them away." This suggests she can pick any subset of the remaining weights. Then "she can only lift and throw away a sequence of weights 2a1, ..., 2ak if and only if ..." So "sequence" here is just a way to denote the list of weights she lifts. It doesn't impose contiguity. The examples: In first sample, they throw away the first three (which are 2^1,2^1,2^2 = 2,2,4) which are contiguous? They are the first three weights in the input order? The input order is 1,1,2,3,3. The first three are indeed 1,1,2 (exponents). They sum to 2+2+4=8, a power of two. They could have chosen non-contiguous as well. So contiguity is not required. So it's any subset.
Thus final answer.
Now, I'll produce a solution in C++ with fast I/O.
Implementation details:
- Use scanf/printf for speed, or cin with ios_base::sync_with_stdio(false).
- n up to 1e6, reading ints is fine.
Pseudo-code:
#include <bits/stdc++.h> using namespace std;
const int MAXW = 1000000 + 50; int cnt[MAXW] = {0};
int main() { int n; scanf("%d", &n); int max_w = 0; for (int i = 0; i < n; ++i) { int w; scanf("%d", &w); cnt[w]++; if (w > max_w) max_w = w; } long long carry = 0; // could be int, but safe. int ans = 0; int i = 0; while (i <= max_w || carry > 0) { long long total = carry; if (i <= max_w) total += cnt[i]; ans += (total & 1); carry = total >> 1; ++i; } printf("%d\n", ans); return 0; }
That's it.
But wait, we used long long for total, but total fits in int. However, it's fine.
Now, think about potential overflow when total = cnt[i] + carry; cnt[i] can be up to 1e6, carry up to maybe 5e5, so total up to 1.5e6, safe.
One more check: In the loop, when i goes beyond max_w, we only add carry. This will process bits until carry is zero. That's correct.
Now, what about the case where max_w is large (1e6) and we have many bits due to carry; our loop may iterate up to max_w + log2(n) which is about 1,000,020, so about 1e6 iterations, which is fine.
Time complexity O(max_w + log n) ≈ 1e6, plus reading n. So overall fast.
Thus solution passes.
Now, I should produce final answer with explanation.
But the user asked for "the minimum number of steps". So output ans.
Edge Cases:
-
All zeros: weights are 2^0 =1? Actually w_i = 0 gives weight 1. So if all zeros, then sum = n. Popcount(n). For n=0? Not possible. But if n is large, okay.
-
Input may contain same w_i many times.
All good.
Thus final answer.
Now I'll write the solution with comments.
But the user might expect a Python solution? The problem is from Codeforces maybe, but they didn't specify language. Usually we can answer in C++ for performance. Since the user didn't specify, I'll provide a C++ solution.
I'll also include reasoning.
Now, produce final output. ```cpp #include #include
using namespace std;
const int MAXW = 1000000 + 50; // wi ≤ 1e6, plus extra for carries int cnt[MAXW] = {0};
int main() { int n; scanf("%d", &n);
int max_w = 0; for (int i = 0; i < n; ++i) { int w; scanf("%d", &w); cnt[w]++; if (w > max_w) max_w = w; } long long carry = 0; // carries from lower bits int ans = 0; int i = 0; // Process bits from least significant to most significant while (i <= max_w || carry > 0) { long long total = carry; if (i <= max_w) total += cnt[i]; ans += (total & 1); // this bit is set in the total sum carry = total >> 1; // propagate carry to next higher bit ++i; } printf("%d\n", ans); return 0;}