4

I have an array of numbers and their gcd if one element is deleted from the array then is it possible to get the new gcd without iterating over all the elements in the array.

e.g the array is 3 6 6 12 clearly the gcd is 3

now if 3 is deleted from the array then the new array becomes 6 6 12 and the gcd is 6

Note: The array may contain duplicates and when the number is deleted then only one instance of that number is deleted from the array.

Ujjwal Prakash
  • 61
  • I'll be very surprised if one could do it faster than it takes to solve the $\gcd$ problem for the remainder of the array. – Jonathan Y. Feb 09 '14 at 10:07
  • Your gcd should be the least positive linear combination of your elements. So the new one should be related to the old by adding a multiple of the number you took out. i.e. they are equivalent modulo the missing number. Perhaps this can help? – Spencer Feb 09 '14 at 10:10
  • Use segment trees – DollarAkshay Jun 07 '19 at 12:44

1 Answers1

2

There is little hope for anything like that. The reason is very simple. For any choice of integers $a_1,\cdots, a_n$, the $gcd$ of the $n+1$ tuple consisting of those integers with $1$ thrown in is, clearly, equal to $1$. That information can't possibly help you to now compute the $gcd$ of the original numbers. So, you can't expect a general procedure to compute the $gcd$ after removing one item, from knowing the $gcd$ of the original list of items (with or without repetition) that will be any better then just computing the $gcd$. If you further specify conditions on the items in the list, then it may be possible to salvage some information to actually speed up the process, though I doubt how much more efficient this would be.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • This tells us that initially having a gcd$=1$ doesn't help. This does not tell us that having a initial gcd$=$(something else) won't help. – Spencer Feb 09 '14 at 10:18
  • true @Spencer, but my example can easily be modified to exclude that possibility as well. Let $g$ be the gcd of the given numbers. Now throw in $g$ itself. The gcd is still $g$. Now can you use that information to deduce the gcd of the original numbers? – Ittay Weiss Feb 09 '14 at 10:21
  • I couldn't use it to produce the original number in one step, but as I pointed out above the new and old gcd are not independent. We know which number we took out (in your example $g$) the gcd's of the original set and the reduced set will be related by, $gcd_{reduced} = k g + gcd_{original}$. It is likely a good algorithm would exploit this relationship to reduce the computation time. – Spencer Feb 09 '14 at 10:29
  • My statement about the gcd's being equivalent modulo the removed number is wrong. I wasn't careful in how I was thinking about the least linear combination property. This does not mean I am convinced that an algorithm doesn't exist which will reduce the computation time. – Spencer Feb 09 '14 at 11:10