QUAD - Editorial ( NCC 2014 )

editorial
, , , ,
1

PROBLEM LINK:

Contest

Practice

Author: Vaibhav Tulsyan, Aditya Sarode

Tester: Vaibhav Tulsyan

Editorialist: Vaibhav Tulsyan

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Binary Arithmetic

PROBLEM:

Given a hex number, split it into two binary numbers, such that first two bits are part of first number and other 2 bits are part of second number. Output their sum (excluding final carry, if present)

QUICK EXPLANATION:

After creating the 2 binary numbers, use basic logic gates to calculate their sum and carry. Output the sum.

EXPLANATION:

Consider input number to be A = Q1Q2Q3…Qn.


Let N<sub>1</sub> be the first binary number and N<sub>2</sub> be the second binary number.
Let Qi = B<sub>1</sub>B<sub>2</sub>B<sub>3</sub>B<sub>4</sub>.
For i in [1,n]:
    Append B1B2 to N1 and B3B4 to N2.

Now, we have to calculate the sum of the two numbers.

Perform binary addition on two numbers N1 and N2 and ignore the carry.
Print exactly 2*N elements.

Complexity: O(N)

1 Like