Sum duplicates in array problem
Create an array $A$ of 1000 elements, indexed from $1$.
Store in $A[i]$ the number of input elements equal to $i$. This can be done in linear time by scanning the input elements once.
Create a list $L$ which will contain at most $1000$ elements (and can hence be implemented using a fixed-size array).
Each element of $L$ is a pair $(m_x, x)$ where $x$ is a number and $m_x &gt; 0$ is the number of its occurrences. Initialize $L$ from $A[i]$ as follows: for each $i$ with $A[i]&gt;0$ append to $L$ the pair $(A[i], i)$ (this can be done in constant time since $A$ contains only $1000$ elements).
From now on the algorithm is trivial, as it is just a simulation of the rules in your question.
Repat:

Search $L$ for the element $(m_x, x)$ with $m_x &gt; 1$ that minimizes $x$.
If such an element does not exist, return the length of $L$.
Otherwise:

Delete $(m_x, x)$ from $L$.
If $L$ contains an element $(m_y, y)$ where $ y = x m_x$ increment $m_y$ by $1$; Otherwise add $(1, x m_x)$ to $L$.



An iteration can be carried out in constant time since all list operations take constant time as well ($L$ always has at most $1000$ elements).
Consider now the quantity $\eta$ defined as the number of elements in $L$ plus the number of elements in $L$ with multiplicity greater than $1$.
Initially $\eta$ is at most $2000$.
In all but the last iteration one of the following two things happens:

An element with $(m_x, x)$ with $m_x &gt; 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and some $m_y$ is incremented (causing $\eta$ to increase by at most $1$).
An element with $(m_x, x)$ with $m_x &gt; 1$ is deleted from $L$ (causing $\eta$ to decrease by $2$) and a new element $(1, x m_x)$ is added to $L$ (causing $\eta$ to increase by $1$).

In any case, each but the last iteration decreases the value of $\eta$ by at least $1$. Since the final value of $\eta$ must be positive, it follows that the total number of iterations is at most $2000 - 1 + 1 = 2000 = O(1)$.
Finally, observe that above procedure only uses constant amount of memory and that any $O(n)$ time and $O(1)$ space algorithm is also a $O(n + k \log k)$ time and $O(k)$ space algorithm, thus also answering your second question.