### nik1996's blog

By nik1996, 15 months ago, , 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]. Comments (9)
 » 15 months ago, # | ← Rev. 8 →   Edit: Wrong solution is wrong, thanks LTDT. WrongBitsets: (1000*1000) time, 1000/32 space. Tested and works with example. int main () { vector 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<
•  » » Consider this test case:7 4 10 8 3We 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 5So the correct answer should be 5 + 3 = 8.Your program prints 7.
•  » » » » I have implemented my solution as a proof of concept.The logic is exactly the same as that in the pseudocode. My code#include #include using namespace std; int n, a; bool dat; vector v, x; int main() { cin >> n; for(int i = 0; i < n; i++) { cin >> a; dat[a] = 1; v.push_back(a); } x.assign(n, 0); while(1) { bool has = false; for(int i = 0; i < (int) x.size(); i++) { while(x[i] < (int) v.size()) { int new_num = v[i] / v[x[i]]; if(v[i] > v[x[i]] && dat[new_num] != 1) { v.push_back(new_num); x.push_back(0); dat[new_num] = 1; has = true; } x[i]++; } } if(!has) break; } cout << v.size() << "\n"; } 
 » 15 months ago, # | ← Rev. 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 using namespace std; int main () { vector nums = {2,100}; bitset<1001> seen; for(int a:nums) seen.set(a); for(int i=0;i