Compare Version Numbers | InterviewBit | Solution Explained
I explain the solution to the problem Compare Version Numbers on InterviewBit in detail. Problem Link.
0. Compare Version Numbers: Problem Discussion
0.0. IO Format
- Given: two strings which are version numbers, ver1 and ver2
- Goal:
- If ver1 > ver2 return 1,
- If ver1 < ver2 return -1,
- otherwise return 0.
0.1. Examples

1. Compare Version Numbers: Observations & Logic
1.0. Intuitions
- the versions are strings, and we need a way to compare the versions
- converting strings to integers will help us compare them
- we know that a version has different numbers split by ‘.’, so we can
- split the string by ‘.’ character
- map all the string values to an integer
- get the list
- we can do all that in python using one single line:
list(map(int, ver.split('.')))

All right! We have extracted the information out of the input. Now what?
We need a way to compare two items in the two lists, simultaneously. So, we can use the zip operator in python3.
class Solution: def compareVersion(self, ver1, ver2): ver1 = list(map(int, ver1.split('.'))) ver2 = list(map(int, ver2.split('.'))) for v1, v2 in zip(ver1, ver2): if v1 > v2: return 1 elif v2 > v1: return -1 return 0
1.1. Implementation Issue
Here’s the thing though, zip only works well if the length of the iterables are the same. That is, only when len(v1) == len(v2) list.
In the case where there is a smaller list, zip will terminate with it.
For example, if we zip([1,2,3], [1,2,3,7])
we will terminate at 3! We will never get a chance to compare 7. So what do we do?
Here lies a key point: if one version is shorter in length to the other, we can append dummy zeroes to it!
For example, if we have a tricky case like [1,3,3,0,0,7]
and [1,3,3]
, we need to be able to pad zeroes like so:

One way to not do this manually is to use zip_longest
from itertools, as the implementation below will show.
2. Compare Version Numbers: Implementation
2.0. Code
from itertools import zip_longest class Solution: def compareVersion(self, ver1, ver2): ver1 = list(map(int, ver1.split('.'))) ver2 = list(map(int, ver2.split('.'))) for v1, v2 in zip_longest(ver1, ver2, fillvalue=0): if v1 > v2: return 1 elif v2 > v1: return -1 return 0
2.1. Code (without zip_longest)
class Solution: def compareVersion(self, ver1, ver2): ver1 = list(map(int, ver1.split('.'))) ver2 = list(map(int, ver2.split('.'))) i, j = 0, 0 m, n = len(ver1), len(ver2) if m > n: ver2.extend([0]*(m-n)) elif n > m: ver1.extend([0]*(n-m)) for v1, v2 in zip(ver1, ver2): if v1 > v2: return 1 elif v2 > v1: return -1 return 0
2.2. Complexity Analysis
- Time:
O(N)
, where N is the number of elements in the longest list, which can be the same order as the number of characters in the string:1.1.1 --> [1,1,1]
- Space:
O(N)
, since we have to store the lists of integers of both the versions separately
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this