Table of Contents
Problem Statement
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, the version number is a string in which numbers are separated by dots. We need to compare the two strings (version numbers) and return which is the latest version (smaller version number).
Input Format
The first line containing a string “s” representing the first version.
The second line containing a string “t” representing the second version.
Output Format
The first and only one line containing “Version1” if “s” is the smaller version number else it contains “Version2”. If both the version are equal then print “Both”.
Example
7.0.1.23 7.0.1.17
Version2
Explanation: Here the value of a,b,c,d in Version1 are 7, 0, 1, 23. And the value of a,b,c,d in Version2 are 7, 0, 1, 17. Version2 is the latest (smaller). Here, we print Version2 in our answer.
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.
Implementation
C++ Program to Compare Two Version Numbers
#include <bits/stdc++.h>
using namespace std;
int CompareVersions(string version1, string version2)
{
for (int i=0,j=0; (i<version1.length() || j<version2.length()); )
{
int v1 = 0, v2 = 0;
while (i < version1.length() && version1[i] != '.')
{
v1 = v1 * 10 + (version1[i] - '0');
i++;
}
while (j < version2.length() && version2[j] != '.')
{
v2 = v2 * 10 + (version2[j] - '0');
j++;
}
if (v1 > v2)
{
return 1;
}
if (v2 > v1)
{
return -1;
}
i++;
j++;
}
return 0;
}
int main()
{
string s,t;
cin>>s>>t;
if(CompareVersions(s, t) == -1)
{
cout<<"Version1"<<endl;
}
else if(CompareVersions(s, t) == 1)
{
cout<<"Version2"<<endl;
}
else
{
cout<<"Both"<<endl;
}
return 0;
}
Java Program to Compare Two Version Numbers
import java.util.Arrays;
import java.util.Scanner;
class sum
{
public static int CompareVersions(String version1, String version2)
{
for (int i=0,j=0; (i<version1.length() || j<version2.length()); )
{
int v1 = 0, v2 = 0;
while (i < version1.length() && version1.charAt(i) != '.')
{
v1 = v1 * 10 + (version1.charAt(i) - '0');
i++;
}
while (j < version2.length() && version2.charAt(j) != '.')
{
v2 = v2 * 10 + (version2.charAt(j) - '0');
j++;
}
if (v1 > v2)
{
return 1;
}
if (v2 > v1)
{
return -1;
}
i++;
j++;
}
return 0;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
String s = sr.next();
String t = sr.next();
if(CompareVersions(s, t) == -1)
{
System.out.println("Version1");
}
else if(CompareVersions(s, t) == 1)
{
System.out.println("Version2");
}
else
{
System.out.println("Both");
}
}
}
152.101.31.144 152.101.31.144
Both
Complexity Analysis to Compare Two Version Numbers
Time Complexity
O(n) where n is the length of the “s” or “t” string which is greater with respect to others.
Space Complexity
O(1) because we don’t use any auxiliary space at here.