ZIO08001- Editorial

editorial
, , , ,
1

Editorialist: Aryan Maskara

Problem Link: ZIO2008 Problem 1

Prerequisites: Observation, Implementation

Problem In Short:
GrayCode(n) encodes the first 2^n whole numbers (i.e 0 to 2^n- 1). It is encoded in the following way:

GrayCode(1) = {0, 1}
GrayCode(2) = 0 * {0, 1} followed by 1 * {1, 0}

Thus, the second part is the reverse of GrayCode(1)

Thus, GrayCode(2) = {00, 01, 11, 10}

Explanation:

Throughout this section, pos refers to the position of the binary code we have to find.

This section is divided into 2 parts:

  1. The code is given, you need to find the position
    Claim: The integers in the code are added to the prefix of the code.
Proof

GrayCode(1) = {0, 1}
GrayCode(2) = 0 * {0, 1} followed by 1 * {1, 0}
Here, we can see that 0 and 1 are attached to the prefix of the code.
(End of proof)

Thus, here we iterate from the right to the left.

Let’s first find out what happens to the position when 0 is attached to the back of a binary code:

Nothing, the position remains the same, as the first part of GrayCode(x) for some x > 1 is nothing but (0*GrayCode(x - 1)).

What happens when 1 is attached to the back of the binary code:

The position changes as 2^{x-1} + (2^{x-1} - 1 - pos) for any x > 0.

Proof

When 1 is attached it forms the second half of GrayCode(x). This starts from (2^x / 2), which is none other than 2^{x-1}.
As the codes are written in reverse order of positions, (1 * the last code in GrayCode(x - 1)) will be equal to the first code in the second half of GrayCode(x)).

We can write the above theory in the form of the equation (2^{x-1} - 1 - pos).

Joining the two equations we get 2^{x-1} + 2^{x-1} - 1 - pos.

(End of proof)

  1. The position is given, you need to find the code.
    The variable i refers to the current index of the binary code we are looking at. It goes from x - 1, x - 2….0, where x is the size of the code.

Example: 1001
Value of x: 3, 2, 1, 0.

Here, we iterate from left to right.

We have 2 options:

  1. If integer < 2^x
    Then the integer belongs to the first half of the code. Thus we add 0 to our answer, and as the codes of the first half are in the same sequence, the integer won’t change.

  2. If integer >= 2^x
    Then the integer belongs to the second half of the code. Note, because the codes are 0-indexed, thus 2^x belongs to the second part. Thus, 2^{x-1} must have been added, so we subtract that. Let’s call this integer newval. Now, the sequence is also in the reverse order. As they are 0-indexed, we will have to subtract 2^{x-1} - 1 - newval.

Thus, the new integer will be:
2^{x-1} - ((2^{x-1} - 1) - newval)

The above observations are enough for subtasks solving.

Solving Subtasks:

Subtask 1

Problem: What is the 7 bit Gray code for the integer 78?

The integer is given, and we have to find the code.

  1. x = 6, and integer >= 2^6 (i.e 64)
    Thus, answer = {1}
    newval = (78 - 64)
    = 14
    New Integer = 63 - 14
    = 49

  2. x = 5, and integer >= 2^5 (i.e 32)
    Thus, answer = {11}
    newval = (49 - 32)
    = 17
    New Integer = 31 - 17
    = 14

  3. x = 4, and integer < 2^4 (i.e 16)
    Thus, answer = {110}
    Nothing else changes

  4. x = 3, and integer >= 2^3 (i.e 8)
    Thus, answer = {1101}
    newval = 14 - 8
    = 6
    New Integer = 7 - 6
    = 1

  5. x = 2, and integer < 2^2 (i.e 4)
    Thus, answer = {11010}
    Nothing else changes

  6. x = 1, and integer < 2^1 (i.e 2)
    Thus, answer = {110100}
    Nothing else changes

  7. x = 0, and integer >= 2^0 (i.e 1)
    Thus, answer = {1101001}

Thus, the final answer is 1101001.

Subtask 2

Problem: What is the 9 bit Gray code for the integer 183?
The integer is given, and we need to find the code.

  1. x = 8 and integer < 2^8 (i.e 256)
    Thus, answer = {0}
    Nothing else changes

  2. x = 7 and integer >= 2^7 (i.e 128)
    Thus, answer = {01}
    newval = 183-128
    = 55
    New Integer = 127 - 55
    = 72

  3. x = 6 and integer >= 2^6 (i.e 64)
    Thus, answer = {011}
    newval = 72 - 64
    = 8
    New Integer = 63 - 8
    = 55

  4. x = 5 and integer >= 2^5 (i.e 32)
    Thus, answer = {0111}
    newval = 55 - 32
    = 23
    New Integer = 31 - 23
    = 8

  5. x = 4 and integer < 2^4 (i.e 16)
    Thus, answer = {01110}
    Nothing else changes

  6. x = 3 and integer >= 2^3 (i.e 8)
    Thus, answer = {011101}
    newval = 8 - 8
    = 0
    New Integer = 7 - 0
    = 7

  7. x = 2 and integer >= 2^2 (i.e 4)
    Thus, answer = {0111011}
    newval = 7 - 4
    = 3
    New Integer = 3 - 3
    = 0

  8. x = 1 and integer < 2^1 (i.e 2)
    Thus, answer = {01110110}
    Nothing else changes

  9. x = 0 and integer < 2^0 (i.e 1)
    Thus, answer = {011101100}
    Nothing else changes

Thus, the final answer is 011101100

Subtask 3

Problem: Which integer is represented by the 10 bit Gray code 1100110011

As mentioned earlier, we will iterate from the end. For simplicity, I will remove the digit when we have finished our operation on it.

Answer = 0.

  1. 1100110011
    Last digit = 1, x = 1.
    Thus, Answer = 2^0 + (2^0 - 1 - 0)
    = 1 + 0
    = 1

  2. 110011001
    Last digit = 1, x = 2.
    Thus, Answer = 2^1 + (2^1 - 1 - 1)
    = 2 + 0
    = 2

  3. 11001100
    Last digit = 0, x = 3.
    Answer remains the same = 2.

  4. 1100110
    Last digit = 0, x = 4.
    Answer remains the same = 2.

  5. 110011
    Last digit = 1, x = 5.
    Thus, Answer = 2^4 + (2^4 - 1 - 2)
    = 16 + 13
    = 29

  6. 11001
    Last digit = 1, x = 6.
    Thus, Answer = 2^5 + (2^5 - 1 - 29)
    = 32 + 2
    = 34.

  7. 1100
    Last digit = 0, x = 7.
    Answer remains the same = 34.

  8. 110
    Last digit = 0, x = 8.
    Answer remains the same = 34.

  9. 11
    Last digit = 1, x = 9.
    Thus, Answer = 2^8 + (2^8 - 1 - 34)
    = 256 + 221
    = 477

  10. 1
    Last digit = 1, x = 10.
    Thus, Answer = 2^9 + (2^9 - 1 - 477)
    = 512 + 34
    = 546

    Thus, the final answer = 546.

Subtask 4

Which integer is represented by the 10 bit Gray code 1011010110?

As mentioned earlier, we will iterate from the end.

Answer = 0.

  1. 1011010110
    Last digit = 0, x = 1.
    Answer remains the same = 0.

  2. 101101011
    Last digit = 1, x = 2.
    Thus, Answer = 2^1 + (2^1 - 1 - 0)
    = 2 + 1
    = 3

  3. 10110101
    Last digit = 1, x = 3.
    Thus, Answer = 2^2 + (2^2 - 1 - 3)
    = 4 + 0
    = 4

  4. 1011010
    Last digit = 0, x = 4.
    Answer remains the same = 4.

  5. 101101
    Last digit = 1, x = 5.
    Thus, Answer = 2^4 + (2^4 - 1 - 4)
    = 16 + 11
    = 27

  6. 10110
    Last digit = 0, x = 6.
    Answer remains the same = 27.

  7. 1011
    Last digit = 1, x = 7.
    Thus, Answer = 2^6 + (2^6 - 1 - 27)
    = 64 + 36
    = 100

  8. 101
    Last digit = 1, x = 8.
    Thus, Answer = 2^7 + (2^7 - 1 - 100)
    = 128 + 27
    = 155

  9. 10
    Last digit = 0, x = 9.
    Answer remains the same = 155.

  10. 1
    Last digit = 1, x = 10.
    Thus, Answer = 2^9 + (2^9 - 1 - 155)
    = 512 + 356
    = 868

Therefore, the final answer is 868.

I hope you understood the solution of the question :slight_smile:

2 Likes