Last Updated: 19 Apr, 2021

Rational Strings

Hard

Asked in company

Problem statement

In ninja land, a rational number is represented as a string in the below format

<IntegerPart> < ‘.’ > <Non-ReaptingPart> < ‘(‘ > <ReaptingPart> < ‘)’ >.

For example,

5 / 1 as ‘5’
12 / 100 as ‘0.12’  
11 / 6 as ‘1.8(3)’
1 / 3 as  0.(3).

There is one flaw in this representation system that a rational number can be represented in more than one string. For example, ‘0.33(3)’ and ‘0.3(3)’ both strings are different but represent the same rational number 1 / 3.

You need to implement a function that verifies if given two strings ‘S’ and ‘T’ of rational numbers represent the same number or not.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains two space-separated strings ‘S’ and ‘T’ denoting the given two strings.

Output Format:

For each test case, print 1 if both strings represent the same number else print 0.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <=  length of <IntegerPart> <= 4
0 <=  length of <Non-ReaptingPart>, <RepeatingPart>  <= 4

<IntegerPart> doesn’t contain leading zeros, except for 0 itself.

Where <IntegerPart>, <Non-ReaptingPart>, and <ReaptingPart> are the part of the given string ‘S’ and ‘T’ according to the format in the problem.

Solve now

Approaches

01 Approach

The idea is to expand both given strings to a fixed length and compare both numbers. A key point to observe here is that we cannot compare strings directly, we have to convert strings into a double value. For example, strings ‘1.0’ and ‘1’ are different but have the same value. So after expanding strings, we compare their double value.

Algorithm:

Let the given strings be ‘S’ and ‘T’.
Declare a global variable say ‘FIX_SIZE’ to store the fixed size of the expanded string, in this case, the max size of the given string can be 15, so we can set the ‘FIX_SIZE’ of the expanded string to be 30.
Declare a function say ‘expand’ to expand both strings and return their double value.
Call ‘expand’ for ‘S’ and ‘T’.
If the returned value for both given strings is the same, then return true, else return false.

Description of ‘expand’ function

This function will take one parameter:

‘S’: String to expand.

double expand ( ‘S’ ):

If ‘S’ doesn’t contain ‘(’ i.e do not have a repeating part then return its double value.
Find the position of ‘(’ in ‘S’ and store it in a variable say ‘CURR_POS’.
Declare an empty string say ‘RET’ to store the resulting string.
Set ‘RET’ to substring ‘S’ from ‘0’ to ‘CURR_POS - 1’, i.e ‘RET’ = ‘S[0 : CURR_POS]’.
Declare a string 'REPEATING' to store the repeating part.
Add 'REPEATING' to the string ‘RET’ until the length of ‘RET’ becomes ‘FIX_SIZE’.
Return double value of ‘RET’.

Solve now

02 Approach

As we know that all rational numbers can be represented in the form of ‘P’ / ‘Q’. Where ‘P’ and ‘Q’ are some integers and ‘Q’ can not be 0. So we will find the corresponding ‘P’ / ‘Q’ for both the given strings and compare them. To find fractional parts for repeating parts, we will use infinite G.P. sum.

For example, consider ‘0.(3)’ i.e. 0.33333…..

This can be written as sum: 0 + 0.3 + 0.03 + 0.003+ 0.0003 + …..

= 0 + 0.3 * (1 + 0.1 + 0.01+ 0.001 + 0.0001 + …..)

Which is an infinite geometric series whose sum is equal to 0.3* (1 / (1 - 0.1 ).

Algorithm:

Let the given strings be ‘S’ and ‘T’.
Declare a function say ‘findFractional’ to find the decimal form of given strings.
If the returned value of the strings is the same then return true, else return false.

Description of ‘fraction’ function

This function will take one parameter:

‘S’: given string whose decimal form we want to calculate.

Double fraction ( ‘S’ ):

Get the nonrepeating part and convert it into double value and store it in a variable say ‘BASE’.
Get the repeating part and store its double value in a variable say 'REPEAT'.
Find the geometric sum with 'R' = 1 / 10 ^ (length of repeating part), where 'R' is the common ratio of geometric series.
Multiply calculated geometric sum with 'REPEAT' and store it in a variable say 'VALUE'.
Return 'BASE' + 'VALUE'.

Solve now