TITLE: How to determine efficiently if the arithmetic addition and subtraction of certain powers of N can be equal to M?
QUESTION [2 upvotes]: I am given a number N and another number M . I have to find out if arithmetic addition and subtraction of certain distinct powers of N  can lead to formation of number M .
I tried different approaches , but not any reliable one.
Also, we can use one power of N only once .Please help.

REPLY [1 votes]: Hints: Use @MarkBennet's idea of expressing $M$ in base $N$.
If $N=2$ then $M$ can be any natural number, and this uses only addition. This can be seen with the binary number system.
If $N=3$ then $M$ can be any natural number, and this may require some subtraction. This can be seen with the balanced ternary system. Also see this.
Play with the powers of $10$ and see which numbers you can get by adding and subtracting distinct powers of $10$. Check out these examples:
$$10001=10^4+10^0$$
$$9999=10^4-10^0$$
$$9000=10^4-10^3$$
$$11111=10^4+10^3+10^2+10^1+10^0$$
$$8889=10^4-10^3-10^2-10^1-10^0$$
$$9091=10^4-10^3+10^2-10^1+10^0$$
See some patterns that you could generalize?

Here is some Pascal-like pseudo-code to find the coefficients of $M$ as distinct powers of $N$. We require $M\ge 0$, $N\ge 2$, and everything to be integers.
i := 0;
do
  digit := M mod N;
  case digit is
  0,1: begin
    coefficient[i] := digit;
    end;
  N-1: begin
    coefficient[i] := -1;
    M := M + 1;
    end;
  else
    raise error "M cannot be written with distinct powers of N"
  end case;
  i := i + 1;
  M := M div N;
while (M > 0);


If you just want to quickly know if such a representation is possible, you could express $M$ in base $N$ notation, then check the following:

The last digit can be $0$, $1$, or $N-1$.
A $0$ or $1$ digit can be preceded by a $0$, $1$, or $N-1$ digit.
A $N-2$ or $N-1$ digit can be preceded by a $0$, $N-2$, or $N-1$ digit.

(The first digit is considered to be preceded by a $0$ digit.) If these conditions are fulfilled, then $M$ can be expressed by adding and subtracting distinct powers of $N$, otherwise not.
A quicker check that catches tells us that some $M$'s are impossible is:

All digits must be $0$, $1$, $N-2$, or $N-1$.
{"set_name": "stack_exchange", "score": 2, "question_id": 1330453}