YosiefAhmed's blog

! Divisible
By YosiefAhmed, history, 13 months ago, In English

Given array with n elements unique values, q query’s two type:

1: change the value of the element to other value which unique(not appear in array).

2: find the minimum value > 1 which not divisible by any other value in arrays

Can any one help me to solve this problem ?

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

»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

not divisible by any number = the minimum prime number that does not appear in the array which is to get the mex of the prime numbers so you can ignore any non-prime number and only consider prime numbers and you can map each prime to its corresponding value .eg 2 -> 1, 3 ->2, 5 -> 3 and so on after that you can have a frequency array and a set and get the mex in O(logn).

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

    Could you explain how to find mex in O(logn) and are we Mapping each prime number to the index of the array?

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      there is no need for mapping or a frequency array I have just noticed that. you can have only a set that contains prime numbers that does not appear in the array. if a prime number is removed then add it to the set. if a prime number is added then remove it from the set. the answer will be the first element in the set(*st.begin())

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the elements are unique, you just need to find the minimum value in the array each time after performing the update operation. If the minimum value turns out to be 1 then there would be no answer for that case since you mentioned it must be greater than 1, otherwise the answer would be that minimum value only, since it is minimum it won't be divisible by any other value in the array.

→ Reply