Compare Two Version Numbers


Difficulty Level Easy
Frequently asked in Adobe Delhivery GE Healthcare GreyOrange MakeMyTrip Wooker Zoho
Pattern Searching String

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions