0
$\begingroup$

Is there any way we can find all the values of x in O(log) or O(1) time complexity.

X + X%5 = 1000

The brute force approach is thinking and putting different values of X and checking with RHS. But the things is I can't think of any other approach other than this for finding the value of X. Is there any other way we can actually find the value of X?

$\endgroup$
1
$\begingroup$

One solution is $X = 1000$. To find another solution, you only need to try values of $X$ in the vicinity of $1000$. For example, $\{999,998,997,996\}$. None of these satisfy the equation, so the solution is $X = 1000$. If the equation were $X - X\%5 = 1000$, then there would be solutions $X = \{1000,1001,1002,1003,1004\}$.

Extending this, the solution to $$X + X\%5 = 10^{18},$$ would be $X = 10^{18}$, and the solution to $$X-X\%5 = 10^{18}$$ would be $X = \{10^{18},1+10^{18},\dots,10^{18}+4\}$.

$\endgroup$
  • $\begingroup$ Thanks a lot. That does seem the right approach. $\endgroup$ – arqam Jun 25 '19 at 17:17
3
$\begingroup$

Let's write $X_5$ for $X\%5$, i.e., $X_5$ is the number such that $X_5 \equiv X \pmod 5$ and $0 \le X_5 < 5$; we must solve $X + X_5 = 1000$. Note that $(X_5)_5 = X_5$. Now, reducing modulo $5$, $$X_5 + X_5 \equiv 0 \pmod 5$$ so $X_5 = 0$. Therefore, since $9996 < X \le 1000$, $X$ = 1000.

This approach avoids any brute-force checking.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.