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.

int main () {
   vector<int> nums = {9,4};
   bitset<1001> cur,next;
   for(int a:nums) cur.set(a); 
   for(int i=1000;i>1;i--)
      if(cur.test(i)) {
         next.set(i);
         for(int j=i-1;j>1;j--) 
            if(cur.test(j))
               next.set(j),next.set(i/j);
         swap(cur,next);
      }
   cout<<cur.count()<<endl; // 3
}

Simple 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:

#include <bits/stdc++.h>
using namespace std;
int main () {
    vector<int> nums = {2,100};
    bitset<1001> seen;
    for(int a:nums) seen.set(a); 
    for(int i=0;i<nums.size();i++) {
        for(int j=0;j<nums.size();j++) {
            if(i==j)continue;
            int next = nums[i]/nums[j];
            if(next==0) next = nums[j]/nums[i];
            if(!seen.test(next)) {
                seen.set(next);
                nums.push_back(next);
            }
        }
    }

    for(int i=1;i<=1000;i++)if(seen.test(i))cout<<i<<" ";
    // 1 2 3 4 5 6 8 9 10 11 12 16 20 25 33 50 100
    cout<<endl<<seen.count()<<endl;
    // 17
}

Yesterday I encountered same problem in IB hiring test! were you able to solve it! coz I have a doubt with specific test case! what will be the output if [9, 9] will be given! will it be 1 ?

Thanks