Rational Strings

Hard
0/120
Average time to solve is 50m
profile
Contributed by
2 upvotes
Asked in company
Apple

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
1.3(3) 1.(3)
45.89 45.87

Sample Output 1:

1
0

Explanation of Sample Input 1:

Test case 1:
Both given strings represent the same rational number that is equal to 1.3333… or 4 / 3.

Test case 2:
String ‘45.89’ and ‘45.87’ do not represent the same rational number.

Sample Input 2:

1
0.(9) 1.0

Sample Output 2:

1

Explanation of Sample Input 2:

Test case 1:
Both the strings represent the same rational no. i.e.1 / 1.
Hint

Expand the given strings.

Approaches (2)
String Expansion

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’.
Time Complexity

O(1)

 

The loop for adding repeating parts of string runs at most 50 times that will take constant time, hence the overall time complexity is constant.

Space Complexity

O(1)

 

We are using strings to store the expanded string but its length will be 50 at most that take constant space. Hence the overall space complexity is constant.

Code Solution
(100% EXP penalty)
Rational Strings
Full screen
Console