nik1996's blog

Expanding Array
By nik1996, 6 years ago, In English

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!!

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

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]).

→ Reply
»
6 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

Edit: Wrong solution is wrong, thanks LTDT.

Wrong
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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
}
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Only distinct elements in the array so [9,9] isn't a valid test case.

    → Reply