2
$\begingroup$

How can I find Nth number such that it is divisible by a OR b? I was thinking to find gcd (Greatest Common Divisor) for both the given numbers (a and b) and use that but I couldn't think of any approach as such.

$\endgroup$
2
  • 1
    $\begingroup$ is the or exclusive or inclusive ? $\endgroup$
    – user451844
    Sep 8, 2017 at 15:43
  • $\begingroup$ It may be easier to work backwards here. It is a common problem to ask "How many integers between $0$ and $m$ are divisible by $a$ or $b$" and the tool to use is inclusion-exclusion. There are $\lfloor\frac{a}{m}\rfloor + \lfloor \frac{b}{m}\rfloor - \lfloor\frac{\text{lcm}(a,b)}{m}\rfloor$ such numbers. Now, the question becomes finding the smallest $m$ such that the above evaluates to $N$. $\endgroup$
    – JMoravitz
    Sep 8, 2017 at 16:18

4 Answers 4

1
$\begingroup$

Suppose $a$ and $b$ are relatively prime and without loss of generality that $a \leq b$. Put $q = b/a$. The sequence will be

$[a, 2a, 3a, 4a, \ldots, \lfloor q\rfloor a, b, \;\;\;(\lfloor q\rfloor+1)a, (\lfloor q\rfloor+2)a, \ldots, 2\lfloor q\rfloor a, 2b, \ldots \ldots,ab, \ldots ]$

For example, if $a=2$ and $b=11$, the sequence is:

$$[2,4,6,8,10,11,12,14,16,18,20,22,\ldots]$$

To compute arbitrary terms in this sequence, we need to keep track of (1) the number of multiples of $a$ we've seen, (2) the number of multiples of $b$ we've seen, (3) the number of multiples of $ab$ we've seen.

Consider the $n$th term in this sequence.

  • Because $a$ and $b$ are relatively prime, we won't see a number in this sequence that's a multiple of $a$ and $b$ until after we've seen $b$ multiples of $a$, and $a$ multiples of $b$— so every $(a+b-1)$ terms. The number of multiples of both we've seen is therefore $C(n)\equiv \lfloor n/(a+b-1)\rfloor$.

  • Approximately every $\lceil q\rceil $th term in this sequence is a multiple of $b$. Hence the number of multiples of $b$ we've seen is $B(n)\equiv \lfloor n/\lceil q\rceil \rfloor$.

  • Every term in the sequence is a multiple of $a$, except the multiples of $b$ alone. Hence the number of multiples of $a$ we've seen is $A(n) = n-B+C$.

The computation is as follows. Given $n$, compute $A(n)$, $B(n)$, $C(n)$. If $n$ is a multiple of $\lceil b/a\rceil$, return $B(n)\cdot b$. Otherwise, return $A(n)\cdot a$.

If you wanted to expand the definitions of everything to write a formula solely in terms of $n$, $a$, and $b$, you might say:

$$D_n \equiv \begin{cases}b\lfloor n/\lceil b/a\rceil\rfloor& \text{if } \lceil b/a\rceil \text{ divides }n\\ a\left(n- \lfloor n/\lceil b/a\rceil\rfloor + \lfloor n/(a+b-1)\rfloor\right)&\text{otherwise}\end{cases}$$


If $a$ and $b$ are not relatively prime, compute their greatest common divisor $d$. Then we can write $a = kd$ and $b=\ell d$, where $k$ and $\ell$ are relatively prime.

To compute the sequence for $a$ and $b$, instead compute the sequence for $k$ and $\ell$, but multiply every term in the sequence by $d$.

$\endgroup$
0
1
$\begingroup$

The process goes through this path

$(1.)$Note that the the position of multiples (of $a$ or $b$) throughout the number line of $\Bbb N$ are repeating image of the positions of them in $(0,$ $lcm(a,b)]$ interval.

$(2.)$We know number of multiples of $a$ in $(x,y]$ is $\lfloor \frac{y}{a}\rfloor -\lfloor \frac{x}{a}\rfloor +1$

$(3.)$Then using $(2)$ in the intervals $(0,b],(b,2b],(2b,3b],...,(lcm(a,b)-b,lcm(a,b)]$ and using $(1)$, I got the following result.

The $N^{th}$ number is, $$j[a,b]+\frac{bn+(N-ij-n)a}{2}+(-1)^{\lfloor\frac{\lfloor\frac{nb}{a}\rfloor+n}{N-ij}\rfloor}\cdot \frac{(N-ij-n)a-bn}{2}$$ where $[a,b]=$lcm of a and b , , $$j=\lfloor\frac{N-1}{i}\rfloor$$ where $$i=\frac{a+b-(a,b)}{(a,b)}$$ $n$ is the maximum integer satisfying $\lfloor n\cdot \frac{b}{a}\rfloor +n\le N-ij$ and $(a,b)$ being gcd of $a$ and $b$.

$\endgroup$
1
$\begingroup$

I saw this problem on SPOJ I am not sure if it the efficient way to solve this problem or not but I got my Solution accepted. Here is the way to solve this problem. if we generate a sequence with a,b and N. the first term will be min(a,b) and the last term will be N*max(a,b). all the numbers which are either divisible by a or b will be in this range.

So we can do a binary search to find that which is Nth term of the sequence. it will be something like this.

    l = min(a,b)
    u =  n*max(a,b)+1
    while(l != u){ 
        mid = l + (u - l) /2
        if(getDiv(a,b,mid-1) >= n)u = mid
        else l = mid + 1
    }

So the Nth term of the sequence will be mid which is the required answer.

where getDiv(a,b,m) are the integers between 0 and m are divisible by a or b". floor(m/a) + floor(m/b) - floor(m/Lcm(a,b));

$\endgroup$
9
  • $\begingroup$ can you please help me to understand your code?I have my solution but it is giving TLE $\endgroup$
    – sunil
    Apr 5, 2018 at 14:14
  • $\begingroup$ Can you tell me which part you did not get? $\endgroup$
    – Lakshman
    Apr 5, 2018 at 14:30
  • $\begingroup$ I have my code but it is giving TLE, I got your one but it is not giving correct answer here hackerearth.com/practice/algorithms/searching/binary-search/… $\endgroup$
    – sunil
    Apr 5, 2018 at 14:32
  • $\begingroup$ ideone.com/NKsc0J this is my code,please help and suggest how i will optimise $\endgroup$
    – sunil
    Apr 5, 2018 at 15:13
  • $\begingroup$ ok you can delete.I will introspect it and will change mine.Thanks lot :) $\endgroup$
    – sunil
    Apr 5, 2018 at 15:20
1
$\begingroup$

$$D_n \equiv \begin{cases}b\lfloor n/\lceil b/a\rceil\rfloor& \text{if } \lceil b/a\rceil \text{ divides }n\\ a\left(n- \lfloor n/\lceil b/a\rceil\rfloor + \lfloor n/(a+b-1)\rfloor\right)&\text{otherwise}\end{cases}$$

This logic doesn't work for $a=5$, $b=9$ & $n=10$ right ?? is there any way to modify this to make this work or am I missing something.

Regards, Devaraj

$\endgroup$
2
  • $\begingroup$ It was difficult to understand your post, but I believe I did. You should use MathJax to make it easier for other users to understand. $\endgroup$
    – Mr Pie
    Sep 13, 2017 at 6:21
  • $\begingroup$ apologies If I am not clear, But as I mentioned above logic of generalizing to find Nth number doesn't holds good for a=5 b=9 right?? Any idea how to improvise this if it can be done. $\endgroup$
    – Deva
    Sep 13, 2017 at 6:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .