Compare Version Numbers

Input/Output Format

Input format: Two Strings depicting the two version numbers of the product to compare.

Output format: The name of the version which is latest.

Example 1

Given two versions of the product, v1 and v2. Compare the two versions, and return the latest version.

Input:

v1 = “1.0.1”
v2 = "1.1"

Output: 

v2 

Explanation:

Here we shall be comparing the strings by their revisions. A number between every two dots is a particular revision, so we’ll compare each revision of the two versions.

v1 has three revisions, 1, 0, and 1.

v2 has two revisions, 1 and 1.

Now on comparing each revision of the two versions:

Revision 1: The first revisions of the two versions are 1 and 1. Since they are the same, we move forward

Revision 2: The second revisions of the two versions are 0 and 1. Since 1 > 0, we return v2 as the answer and stop further iterations.

Example 2

Given two versions of the product, v1 and v2. Compare the two versions, and return the latest version.

Input:

v1 = “1.0”
v2 = “1.0.0”

Output: 

v1

Note: v2 is also correct, as v2 is the same as v1.

Explanation:

Here also, we shall be comparing the strings by their revisions. A number between every two dots is a particular revision, so we’ll compare each revision of the two versions.

v1 has three revisions, 1, 0, and 0.

v2 has two revisions, 1 and 0.

Now on comparing each revision of the two versions:

Revision 1: The first revisions of the two versions are 1 and 1. Since they are the same, we move forward

Revision 2: The second revisions of the two versions are 0 and 0. Since they are also the same, so we move forward

Note: Here, v1 has only two revisions, whereas v2 has three revisions. So to compare them, we take v1 as three revisions, with the last revision being 0.

So now v1 becomes “1.0.0”, and v2 is “1.0.0”; since they are the same, we return any of the two strings as the answer.

Approach

We will be following the two-pointer approach to solving this problem. We will isolate each revision from the version number separately and compare the corresponding revision with the other string. Here are the steps which we will be following to compare the revisions

Algorithm

Isolate the revisions: Separate all the revisions of the version number. For this, we will be constructing a list/array of strings; each element represents a revision number.

E.g., Consider the string v1=”1.0.1” 

So we will be splitting the string into a list of 3 elements, each element representing the revision number 

So our list becomes 

v1 = [“1”,”0”,”1”]

Similarly, we will be creating a list/array of elements of v2="1.1"

We get 

v2 = [“1”,”1”]

 

Converting the datatypes: Now, we will convert all list elements to integers. This will help us in removing the trailing zeroes, as well as an easy comparison between the two numbers.

Two pointers: Now, for comparing the corresponding values from the two arrays, we have to make the two arrays of the same length. So we will be padding the shorter array with zeroes to make its length as same as the other one. 

Now that we have two arrays of the same length, we take two pointers, i and j, where i traverse the string v1 and j traverse the string v2. 

Now we compare the corresponding values of the two pointers

v1 [ i ] == v2 [ j ] 

If the corresponding value is equal, then we move forward. Once we encounter a value greater than the other, we stop the iteration and return the answer. 

Dry Run

Let’s see the above approach with an example, to understand better. 

Example

Consider these two versions of the product, v1 and v2. 

v1 = “1.0.1”

v2 = “1.1”

Step 1: We will be isolating the revisions from the version number.

Let’s make the array with revisions as elements.

Step 2: Convert the elements into integer datatype.

If any element had trailing zeroes, converting the string to an integer also helps remove those.

Step 3: Make the length of the two arrays equal.

We had the shorter array with zeroes to make them equal.

Step 4: Now take two pointers, i and j, where I point to v1 and j points to v2.

And start comparing the corresponding values.

So we increment both i and j 

Since we get v2_arr > v1_arr, we return v2 as our answer.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

/*  
    function to split string to array of strings.
    via a seperator
*/
vector<string> split_into_revisions(string version) {

    vector<string> split_arr;
    string str;

    // stringstream object referencing version string
    stringstream ss(version);

    /*
        checking the getline() function condition.
        " . " acts as seperator
    */
    while (getline(ss, str, '.'))
        split_arr.push_back(str);

    // returns the array of revisions
    return split_arr;
}

int main() {

    // input
    string version1 = "1.0.1";
    string version2 = "1.1";

    // split the strings into vector of revisions
    vector<string> v1 = split_into_revisions(version1);
    vector<string> v2 = split_into_revisions(version2);

    // length of padding to insert
    int high = v2.size();
    int low = v1.size();
    int diff = abs(high - low);

    // vector to pad with 0 (zeroes)
    if (v1.size() > v2.size()) {
       for (int i = 0; i < diff; i++) {
           v2.push_back("0");
       }
    }
    else {
       for (int i = 0; i < diff; i++) {
           v1.push_back("0");
       }
    }

    vector<int> val1, val2;

    for (int i = 0; i < v1.size(); i++)
        val1.push_back(stoi(v1[i]));

    for (int i = 0; i < v2.size(); i++)
        val2.push_back(stoi(v2[i]));

    // two pointer to compare the corresponding indices
    int i = 0;
    int j = 0;

    // if the versions are same, then return any version
    string ans = "Version 1";
    while (i < val1.size() and j < val2.size()) {
        if (val1[i] > val2[j]) {
            ans = "Version 1";
            break;
        }
        else if (val1[i] < val2[j]) { 
            ans = "Version 2";
            break;
        }
        i++;
        j++;
    }

    // returns the string
    cout << ans << endl;
    return 0;
}

Output

Implementation in Java

class Main {
 public static void main(String args[]) {

       // input
       String version1 = "1.0.1";
       String version2 = "1.1";

       // spliting the strings into revisions
       String v1[] = version1.split("\\.");
       String v2[] = version2.split("\\.");

       // padding the array with extra '0'
       int max_len = Math.max(v1.length, v2.length);
       int val1[] = new int[max_len];
       int val2[] = new int[max_len];

       for (int i = 0; i < v1.length; i++)
           val1[i] = Integer.parseInt(v1[i]);
       for (int i = 0; i < v2.length; i++)
           val2[i] = Integer.parseInt(v2[i]);

       // comparing the two pointers side by side
       for (int i = 0; i < max_len; i++) {
           if (val1[i] > val2[i]) {
               System.out.println("Version 1");
               return;
           }
           if (val1[i] < val2[i]) {
               System.out.println("Version 2");
               return;
           }
       }

       System.out.println("Version 1");
       return;
   }
}

Output

Implementation in Python

def get_revision_list(version: str) -> list:

   # gets the list of revisions of version
   return version.split(".")

def increase_length(array: list, low: int, high: int) -> list:
   # increases the length of list
   # appends/pads the array with 0 (zeroes)

   array.extend(["0"] * abs(high - low))
   return array

def compare_version(version1: str, version2: str) -> str:
   # function to compare the two versions
   
   v1, v2 = get_revision_list(version1), get_revision_list(version2)
   v1 = increase_length(v1, len(v1), len(v2))
   v2 = increase_length(v2, len(v1), len(v2))

   # type-casting the revisions from string to int
   v1, v2 = map(lambda char: int(char), v1), map(lambda char: int(char), v2)

   # traversing the two versions simultanously (two-pointer)
   for n1, n2 in zip(v1, v2):
       if n1 > n2:
           return "Version 1"

       elif n1 < n2:
           return "Version 2"
   return "Version 1"

# driver code
version1 = "1.0.1"
version2 = "1.1"
print(compare_version(version1, version2))

 
Output

Complexity Analysis

So let’s discuss the complexity analysis of the implementation above.

Time Complexity: Since we are traversing two arrays, and in the worst case, if both arrays are the same, we must traverse the entire array. So our time complexity reaches O(max(v1,v2)), or if n denotes the length of the longer array, our worst-case time complexity goes O(n).

Space complexity: Since we are creating an array of revisions of the version number. So our space complexity reaches the order O(max(number of revisions in v1, number of revisions in v2)). So, if n denotes the maximum number of revisions among the two arrays, our space complexity reaches O(n).

Also see, How to Check Python Version in CMD

Frequently Asked Questions

How to compare two arrays according to their values?

We take two pointers, i and j, pointing to two arrays. Next, we compare the corresponding values and move the two pointers forward. If one of the values is greater than the other at any instant, we get the larger array (according to the value). 

How to change the datatype / typecast datatype of all the elements in the array?

We can use a map or transform (in the case of C++), to solve this problem. It takes a function as an argument, which gets applied to all the elements of the iterable. 

So to convert a list of strings to a list of integers, we use a map, with the function taking char as a parameter and returning its integer typecase. So the values get converted into integers.

How to split a string into an array of elements?

Many languages support the inbuilt function called split, which takes a character as a parameter and is applied over a string. It returns an array of strings, separated by the separation character taken as a parameter. 

How to join an array of strings to one string?

For joining the list of strings, we take an empty string. Then we iterate over the array and concatenate the elements into the empty string. On reaching the end, we got one string formed from an array of strings. Many languages have an inbuilt join function for this functionality. 

How to handle the case when one pointer reaches the end of an array while the other doesn’t?

We either pad the array with any integer/empty strings to make its length equal to the other array and then compare the corresponding values. Or we could have two while loops, one traversing the common size of both and the other traversing the extra length.

Also Read - Strong number in c

Conclusion

So, Ninjas, I hope you can now quickly determine the latest version of any product. 

In this article, we learned how to compare two product versions to determine which is the latest. We follow the two-pointer approach for the same. 

We hope this has helped you to increase your understanding of Two Pointers and how to check if two arrays of strings/characters are the same. If you want to learn more about such topics, do read more of our articles

• Comparing Strings
• Various data types in C++
• Splitting a string into array
• Introduction to C#
   

If you want to study more about Two Pointers and practice the questions that require you to take your basic knowledge on these topics a bit higher, you can visit our Guided Path for DSA on  Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Courses. Until then, All the best for your future endeavors, and Keep Coding.