# 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 Compare Version Numbers: sample test case

## 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('.')))` Compare Version Numbers: converting the string to a list of integers

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(*(m-n))
elif n > m:
ver1.extend(*(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

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

1. Srishti Chopra :July 23, 2022 at 11:29 am
2. Makarand :August 16, 2022 at 11:06 am