Compare Version Numbers

Easy
0/40
Average time to solve is 10m
profile
Contributed by
66 upvotes
Asked in companies
SalesforceCerner Corporation

Problem statement

You are given two versions numbers A and B as a string. Your task is to compare them and find out which one of them is a newer version.

Note: 
There are no leading zeros in any of the strings except in the case of zero itself. Note that, the leading zeroes are not allowed even after a '.' ie: 121.005 is an invalid version, while 121.5 is an valid version.
For Example: 
A = “1.23.45”, B = “1.23.456”

The first two parts of both the strings are the same i.e 1 and 23 and the third part of B is greater than the third part of A i.e. 45 < 456, thus string B is the latest version.
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. Then, the T test cases follow.

The first line of each test case contains version A as a string.

The second line of each test case contains version B as a string.
Output format: 
For each test case, print 1 if version A is latest, -1  if version B is latest and 0 if both versions are the same.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
1 <= T <= 10
1 <= |A|, |B| <= 10^5

All the string A and B characters contain digits and dots only and both the strings are started and terminated by a digit.
Sample Input 1:
2
1.2.4
1.2.3
10.2.2
10.2.2
Sample Output 1:
1
0
Explanation for Sample Input 1:
For the first test case, the first two parts of both the strings are the same but the third part of the 1st version is bigger than the 2nd version. Hence our answer is 1

For the second test case, both the versions are identical here, so the answer will be 0.
Sample Input 2:
2
123.45
123
1.0.0
1
Sample output 2:
1
0
Hint

Think of a iterative comparison approach

Approaches (1)
Iterative Approach

First of all, we will delete the zeros from the end of both the strings. For example: Convert 1.0.0 to 1, and  2.2.0 to 2.2 etc.

 

Now, the idea is to use an iterative approach to compare both strings.

 

We will use four-pointers start1,end1 (pointing to version A) and start2,end2 (pointing to version B) all initialized 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) now If :

 

  • end1 > end2
    • Version A is the latest
  • end2 > end1 
    • Version B is the latest
  • end2 = end1
    • In this case, we will compare both the strings from their respective start points and endpoints and output the result of the comparison. If both the strings are equal we will move start1 to end1 and start2 to end2 and will do the same process 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.

Time Complexity

O(N + M), where M and N are the lengths of the string A and B respectively.

 

In the worst-case, all the characters of both strings will be iterated so the overall time complexity will be   O(N + M)

Space Complexity

O(1).

 

In the worst case, constant space is required.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Compare Version Numbers
Full screen
Console