### 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8960564,"math_prob":0.98325306,"size":2704,"snap":"2020-34-2020-40","text_gpt3_token_len":709,"char_repetition_ratio":0.10555556,"word_repetition_ratio":0.008064516,"special_character_ratio":0.28550297,"punctuation_ratio":0.1294719,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99699455,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,7,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-04T20:47:56Z\",\"WARC-Record-ID\":\"<urn:uuid:0256acde-fb57-4032-b30c-2301460d282b>\",\"Content-Length\":\"118804\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:29735536-0e51-45b7-99f2-76851b5c56b0>\",\"WARC-Concurrent-To\":\"<urn:uuid:694ac517-c4a3-4f5e-8250-2de4c58556fc>\",\"WARC-IP-Address\":\"81.27.240.126\",\"WARC-Target-URI\":\"http://codeforces.com/blog/entry/66825\",\"WARC-Payload-Digest\":\"sha1:45GUOOYT6EKKH4V56NFKE546F5V2YMQA\",\"WARC-Block-Digest\":\"sha1:KPCBCRZMT6TXAGTC7DAF5QNQ4KT2DKND\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439735882.86_warc_CC-MAIN-20200804191142-20200804221142-00407.warc.gz\"}"}