How to deny base numbers?

Question

Recently I was given the Codility test, and I was wondering how can I deny the -2 base digits?

For example, the array [1,0,0,1,1] represents 9 in the database -2 :

 -2 bases: 1,-2,4,-8,16 1 + (-8) + 16 = 9 [1,0,0,1,1] 

Negative 9 in the database -2 :

 -2 bases: 1,-2,4,-8 1 + (-2) + -8 = -9 [1,1,0,1] 

I am ignorant of the issue. There must be some intuitive solution for this. Do you have any clues?

Answer 1

In the base & minus 2, 1 in position i means (-2) ⁱ .

Thus, [1,1] in the positions [i, i + 1] means (-2) ⁱ + (- 2) ^{i + 1} = (- 2) ⁱ + (- 2) (- 2) ⁱ = (1 + -2) (- 2) ⁱ = -. (- 2) ^I

Thus, you can undo any occurrence of [1,0] by changing it to [1,1] and vice versa.

Any other occurrences of 0, of course, can be left unchanged: -0 = 0.

So, in your example, we divide [1,0,0,1,1] by [{1,0}, {0}, {1,1}], deny each part to get [{1,1}, {0}, {1,0}], i.e. [1,1,0,1,0], and remove the unnecessary high 0, creating [1,1,0,1].

Answer 2

Try some examples:

  (16 -8 4 -2 1) 1 = 0 0 0 0 1 -1 = 0 0 0 1 1 2 = 0 0 1 1 0 -2 = 0 0 0 1 0 3 = 0 0 1 1 1 -3 = 0 1 1 0 1 4 = 0 0 1 0 0 -4 = 0 1 1 0 0 5 = 0 0 1 0 1 -5 = 0 1 1 1 1 

We can try to determine this mathematically:

The specified input i (b) (where B is a bit),

• i = Σ (-2) ^b i (b) - definition of the base -2)
• O = -I is what we are trying to solve for
• O = -Σ (-2) ^b i (b) - substitution
• O = Σ - (- 2) ^b i (b) - distribution
• - (- 2) ^b = (-2) ^b + (-2) ^{b + 1}
• O = Σ ((- 2) ^b + (-2) ^{b + 1} ) i (b) - permutation
• O = Σ ((- 2) ^b i (b) + (-2) ^{b + 1} i (b)) - substitution
• O = Σ (-2) ^b i (b) + Σ (-2) ^{b + 1} i (b)
• O (b) = i (b) + i (b-1)

Now this leaves the possibility that O (b) is 0, 1 or 2, since I (b) is always 0 or 1.

If O (b) is 2, that is, a “carry”, consider a few examples of transfers:

  (16 -8 4 -2 1) (16 -8 4 -2 1) 1+1 = 0 0 0 0 2 = 0 0 1 1 0 -2-2 = 0 0 0 2 0 = 0 1 1 0 0 4+4 = 0 0 2 0 0 = 1 1 0 0 0 

for each b, starting from 0, if O (b)> = 2, subtract 2 from O (b) and the increments O (b + 1) and O (b + 2). Do this until you reach your maximum value.

Hope this explains it in some detail.

Answer 3

Imagine you have number A. Then -A = A - 2 * A Or -A = A + (-2) * A. Fortunately, you have a base of -2. And (-2) * A is equivalent to a left shift by one digit. All you need now is just to implement A & lt; & lt; 1 + A. Array offset is easy. And then you need to implement binary addition with one slight difference: every time you carry a bit, you need to multiply it by -1.

 public int[] solution(int[] input) { var A = new int[input.Length + 1]; var B = new int[input.Length + 1]; input.CopyTo(B, 1); input.CopyTo(A, 0); return GetResult(A, B).ToArray(); } public IEnumerable<int> GetResult(int[] A, int[] B) { var r = 0; for (int i = 0; i < A.Length; i++) { var currentSum = A[i] + B[i] + r; r = -currentSum / 2; yield return currentSum % 2; } } 

Sorry, but an example in C #