nik1996's blog

By nik1996, 6 months 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

»
6 months 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]).

»
6 months ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

Edit: Wrong solution is wrong, thanks LTDT.

Wrong
  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

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

        Let the original array be A.

        1. Keep an array, X, of n indexes. Initialize all values to 0.
        2. Do an infinite loop. Let this be loop 1
        3. Loop through X within the infinite loop. Let this be loop 1.1
        4. For the ith value in X, if i is not equal to X[i] and A[i] > A[X[i]], append A[i] / A[X[i]] to A if not already present. Add an additional 0 to X to account for any new element in A.
        5. Increment X[i] by 1.
        6. Once X[i] has reached the end of A, we go to the next element in X.
        7. If loop 1.1 does not add any new numbers to A, we break from loop 1.
        8. Print size of 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).

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

        I have implemented my solution as a proof of concept.

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

        My code
»
6 months 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
}