Last Updated: 25 Dec, 2020
Compare Versions
Moderate
Asked in companies
You are given two strings ‘Version1’ and ‘Version2’ representing the version numbers. Your task is to compare them and find out which one of them is the latest version.
Note:
The input strings consist of digits and dots only and both the strings are started and terminated by a digit. There are no leading zeros and no zeros following a dot in both the strings except in the case of zero itself.
For Example:
Version1 = “1.23.45”, Version2 = “1.23.456”
The first two parts of both the strings are the same. The third part of Version2 is greater than the third part of Version1, thus string Version2 is of the latest version.
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case contains the string ‘Version1’.
The second line of each test case contains the string ‘Version2’.
Output format:
For each test case, print 1 if version 1 is latest, -1 if version 2 is latest and 0 if both versions are the same.
Print output of each test case in separate lines.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= |Version1| <= 10000
1 <= |Version2| <= 10000
Time limit: 1 second
Approaches
The idea is to use a recursive approach to compare the versions. Here we will start iterating through both the strings to extract the number till we reach a dot (or the end of the string) and we will compare both the numbers. If they are the same, we will recursively compare the remaining string. If they are different, we will find out which one of them is bigger and will return the result of the comparison as our answer.
To compare the number represented as strings, we will need to design a function.
The working of comparison function can be understood as:
- If the length of string Version1 is greater than the length of string Version2 -
- In this case, the number in string Version1 is greater.
- If the length of string Version2 is greater than the length of string Version1 -
- In this case, the number in string Version2 is greater.
- If the length of string Version1 is equal to the length of string Version2 -
- Here we will traverse both the strings and find the first different character pair and compare them and output the result. If no such character pair exists, then we will return 0 as both the strings are the same.
The idea is to use an iterative approach to compare both strings. The approach is similar to the previous approach just that we will be doing it in an iterative manner.
We will use four pointers ‘start1’, ‘end1’ (pointing to string Version1) and ‘start2’, ‘end2’ (pointing to string Version2) all initialised to 0. We will move ‘end1’ to the first dot to the right of ‘start1’ (or the end of the string if no such dot exists) and we will move ‘end2’ to the first dot to the right of ‘start2’ (or the end of the string if no such dot exists).
If :
- ‘end1’ > ‘end2’
- String Version1 denotes the latest version.
- ‘end2’ > ‘end1’
- String Version2 denotes the latest version.
- ‘end2’ == ‘end1’
- In this case, we will compare both the strings from their respective start points to endpoints and output the result of the comparison.
- If both the parts are equal, we will move ‘start1’ to ‘end1’ and ‘start2’ to ‘end2’ and compare the remaining strings iteratively.
- If we reach the end of both the strings without terminating this means that both the strings are equal and we will return 0 in this case.