Solved-A4- Solution

Description

Hackerrank Link: https://www.hackerrank.com/inheritance-1580620337

Objective

● Learning basic inheritance, modular arithmetic, and number-theoretic algorithms.

Data Structure

Create classes in C++ for representing Complex, Rational and Natural numbers. These classes should support the following functionality:

1. Complex: add, subtract, multiply

2. Rational: add, subtract, multiply, reduce

3. Natural: check prime, calculate inverse modulo prime p

Create an inheritance structure between the classes to reuse code. The inheritance can be multilevel, Complex —> Rational —> Natural, meaning that Rational inherits from base class Complex and Natural inherits from Rational.

The reduce operation means, given a fraction p/q, obtain p’/q’, where GCD(p’, q’) coprime. Eg: reduce(6 / 9) = 2 / 3. In modulo narithmetic, if the inverse of numis (num * inv _num) % n = 1.Refer to Modular arithmetic rulesand Fermat’s theory related to modular arithmetic and calculation of inverse modulo p.

= 1, or p’ and q’ are

inv_num,then:
Little Theoremfor

Some useful links for number-theoretic algorithms: Euclid’s GCD algorithm, Sieve algorithm, Modular arithmetic rules, Fermat’s Little Theorem, Fast exponentiation

Input Format

For every test case, the first line contains n, the number of operations that follow. Each operation will be of the form , where number type can be {“complex ”, “rational”, “natural”} and operation type depends on number type. The allowed operations for complex are {“add”, “sub”, “mult”}, for rational they are {“add”, “sub”, “mult”, “reduce”} and for natural they are {“isprime”, “inverse”}. This line will be followed by the actual inputs for each operation

Complex numbers in the input are represented as: with both numbers as double. Rational numbers in input are represented as: with both numbers as integers.

Arithmetic operations(add , sub, mult) over complex numbers and rationals will be followed by 2 lines containing 1 number each represented in the above-specified format. The reduceoperation on rationals will be followed by 1 rational number represented as specified above. All operations on natural numbers are followed by a single number. The prime p with respect to which inverse modulo p should be evaluated is 1000000007.

Output Format

Print output for each operation in a separate line. Print complex numbers in the same format as the input. Print both real as well as imaginary parts of the complex number even if any of them is 0. For rationals, print the double representation of the rational for all operations except reduce. For the reduceoperation over rationals, print 2 integers , with the first integer being negative if the result is negative. For the isprimeoperation, print 0/1 if the number is not prime/ prime respectively and for the inverse mod p print a single natural number.

Constraints
Number of operations: 1 <= n <= 105. For complex numbers: -103<= real, imaginary <= 103, for
rationals: -104<= num, denom <= 104, denom != 0, and for natural: 1 <= number <= 106. Sample Testcase Input: 9 complex add —> number type and operation type

1.2 2.3 —> 1st number: 1.2 + 2.3i

2.1 1.3 —> 2nd number: 2.1 + 1.3i

complex sub

1.2 3.1
2.2 1
complex mult
-1 2
2.3 1.2
rational add
1 2 —> 1/2
1 3 —> 1/3

rational sub

1 400

1 200 rational mult

1 2

24 6

rational reduce

210 14

natural isprime

101

natural inverse

123456

Output:

3.300 3.600

-1.000 2.100

-4.700 3.400

0.833

-0.003

2.000

15 1

1

78351802

Design Submission Format

For the design submission on Moodle, please submit a .tar.gz file named as your roll number.

Note

All doubles have to be printed with a fixed precision of 3 decimal digits similar to the assignment A3.

Number Display

3.4 3.400

3.1415 3.142

2 2.000

This style of printing can be set by using the following statements before any “cout”. You only need to write these statements once:

std::cout.precision(3); std::cout << std::fixed;