Hello codeforces!!

Recently I was attempting an hiring test and came across the following problem which I could not solve. Could anybody help me in solving this problem?

You are given a special type of array — an expanding array. An expanding array is an array which has only distinct elements and keep expanding based on the following process:

- Pick any 2 integers (A and B, A > B) randomly from the existing expanding array. If integer part of A / B (lets call it Z) is not present in the array, we expand our original expanding array and add Z to it.

Keep repeating above operation until array cannnot be extended further. Find the final size of expanding array.

*Constraints:* Array size <= 500, each array element Arr[i]: 1<=Arr[i]<=1000.

*Example:* I/P : Arr = [9, 4], O/P : 3, Final expanding array is :[9,4,2].

Thanks in advance!!

Let's consider a smart brute force approach.

For every unique value in the array, store a list of unique elements that are less than it. Now we do A / B for every A > B. For each A, when you do A / B, remove B from A's list. Now, when the new integers are generated, add them to the corresponding lists. Remember not to add the new integer to a list if it was previously removed.

Since every number is inserted into every list once and removed from every list once. And there are at most 1000 numbers and 1000 lists, the time complexity of this solution is O(N^2) where N = Max(Arr[i]).

Edit: Wrong solution is wrong, thanks LTDT.

WrongBitsets: (1000*1000) time, 1000/32 space. Tested and works with example.

Consider this test case:

7 4 10 8 3

We can take $$$ \lfloor{\frac{4}{3}}\rfloor = 1 $$$, $$$ \lfloor{\frac{8}{4}}\rfloor = 2 $$$ and $$$ \lfloor{\frac{10}{2}}\rfloor = 5 $$$.

The final array will be:

7 4 10 8 3 1 2 5

So the correct answer should be 5 + 3 = 8.

Your program prints 7.

I stand corrected, could you write (pseudo) code of your solution? It's not very clear to me.

The pseudocode below varies quite a bit from my original description to simplify implementation.

Let the original array be A.

You can clearly see that there are at most 1000 elements in X. And any X[i] can be incremented at most 1000 times. Hence, this algorithm is O(max(A[i])^2).

I have implemented my solution as a proof of concept.

The logic is exactly the same as that in the pseudocode.

My codeSimple 2 nested for loops with marking already added numbers and trying a new with each of the others O(N^2) time, O(N) space: