wish_me's blog

Elements of an array that are not divisible by any element of another array
By wish_me, history, 7 years ago, In English

Given two arrays A[] and B[], write an efficient code to determine if every element of B[] is divisible by at least 1 element of A[]. Display those elements of B[], which are not divisible by any of the element in A[].

Examples:

Input : A[] = {100, 200, 400, 100, 600}

B[] = {45, 90, 48, 1000, 3000}

Output : 45, 90, 48

The output elements are those that are

not divisible by any element of A[].

n<10^5 arr.size<10^5

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Good day to you,

Well firstly, somehow "store" elements of A. Somehow I don't see the "size" of elements so I can't choose the best yourself:

  1. Store them in MAP

  2. Mark them in an array (or bitset)

  3. Sort them and then binary search for them

(There might be some more, yet at least one shall work — complexity might differ obvously :) )

Now for each element of array B, factorize it (Again — it depends on size of integers). A will also propose you some factorisation methods:

  1. Iterate to all numbers to (this is slowest but easiest)

  2. Do similar thing as in 1 but do it with PRIMES only (much faster, since primality is very sparse attribute)

  3. Do sieve, and remember divisors (This one is the fastest, yet works only for low numbers)

  4. Pollard-Rho (Very fast, yet the hardest one)

Again there are some more ways, but these shall be enough.

Now, assemble them back into all kinds "divisors" and check, whether each divisor is/isn't in the structure you chose in first step. Assemble might be done by "simple" recursion :).

WARNING: This solution might/might not pass depending on given TIME-LIMIT and size of integers (for example strong input for 10^18 migh probably beat it- dunno )

Hope it helped a little bit.

Good Luck & Have Nice Day ^_^

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

Limit for the values in A and B?

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

    A & B are less the 10^5

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

      I suppose you meant now that the values are <= 10^5 (not the length). So for that we can use an idea similar to sieve. we can maintain an array of booleans of size (10^5 + 1), let's call it Z. Then we iterate through each element in A, and do the following (now we're on index i):

      if (Z[A[i]] is false):
    for (j = A[i]; j <= 10^5; j += A[i])
        Z[j] = true;

      Then to find the answer, for each element in B, say B[i], we can just check Z[B[i]]: if it's true then B[i] is divisible by at least one element in A, or it isn't divisible by any element in A otherwise.

      → Reply