Given two input strings, which are in form of version numbers. A version number looks like a.b.c.d where a, b, c, d are integers. Therefore, version number is string in which numbers are separated by dots.
We need to compare the two strings (version numbers) and return which is latest version (smaller version number)
Examples
Input strings,
Version1 : 7.0.23
Version2 : 7.0.17
Output : Version2 is latest (smaller)
Here, Version2 < Version1
Time complexity : O(n)
Algorithm
1. Traverse both the input strings
2. Store the values before ‘.’ in v1 and v2.
3. Compare v1 and v2.
4. If v1 < v2, return -1 or If v1 > v2 return 1.
5. Else, return 0. Do this till the end of strings.
C++ Program
#include <bits/stdc++.h>
using namespace std;
int CompareVersions(string version1, string version2)
{
//Initialize integer part with zeroes
int v1 = 0, v2 = 0;
//Traverse the entire string
for (int i=0,j=0; (i<version1.length() || j<version2.length()); )
{
//store integer value of version2 in v2
while (i < version1.length() && version1[i] != '.')
{
v1 = v1 * 10 + (version1[i] - '0');
i++;
}
//store integer value of version2 in v2
while (j < version2.length() && version2[j] != '.')
{
v2 = v2 * 10 + (version2[j] - '0');
j++;
}
if (v1 > v2)
{
return 1;
}
if (v2 > v1)
{
return -1;
}
//If equal reset v1 and v2 and move forward in the string
v1 = v2 = 0;
i++;
j++;
}
return 0;
}
//Main functions
int main()
{
string version1 = "7.0.21";
string version2 = "7.0.17";
if(CompareVersions(version1, version2) == -1)
{
cout<<version1<<" is smaller(latest) than "<<version2<<endl;
}
else if(CompareVersions(version1, version2) == 1)
{
cout<<version2<<" is smaller(latest) than "<<version1<<endl;
}
else
{
cout<<"Both versions "<<version1<<" and "<<version2<<" are equal\n";
}
return 0;
}
