Given two strings N and M in the form of a * 10 b. The task is to compare given two floating-point numbers and print the smaller number and if both the numbers are equal then print Equal.
0<|a|<10^9 and -10^9<b<10^9.
Example:
N and M are two numbers with two parts:
- a1 is mantissa of N and a2 is mantissa of M.
- b1 is exponent of N and b2 is exponent of M.
Input: N = 3*10^2, M = 299*10^0
Output: M
Explanation:
a1 = 3, b1 = 2
a2 = 299, b2 = 0
N = 3*10^2 = 300
M = 299*10^0 = 299.
We know that 299 is smaller than 300.Input: N = -5*10^3, M = -50*10^2
Output : Equal
Explanation:
a1 = -5, b1 = 3
a2 = -50, b2 = 2
N = -5*10^3 = -5000
M = -50*10^2 = -5000
Hence, N and M are equal.Input: N = -2*10^1, M = -3*10^1
Output: M
Explanation:
a1 = -2 , b1 = 1
a2 = -3 , b2 = 1
N = -20
M = -30
-30 is less than -20, hence M is smaller number.
Naive Approach: We will calculate the values of numbers extracted from strings N and M and then compare which one is better. The bigInteger class will be used for storing and calculating the value of N and M in Java. This approach can give Time Limit Exceeded error for larger test cases.
Optimal Approach:
- Extract mantissa and exponents from both the strings N and M.
- Find the index of ‘*’ ( let say mulInd), then substring before mulInd will be mantissa(a1).
- Find the index of ‘^’, let say powInd, then substring after powInd will be exponent(b1).
- Similarly, find out a2 and b2.
- if(a1 > 0 && a2 < 0), print M ( M will always be smaller).
- Similarly, if (a2 > 0 && a1 < 0), print N.
- else there will be need to use log to compare.
- The following formula will be used to calculate the log and arrive at a result that will be compared to determine which number is larger.
N = a1 * 10 ^ b1
Taking log base 10 both side
log N = log(a1) + b1 ———-(1)
Similarly, log(M) = log(a2) + b2 ———(2)
Subtract equation (1) from equation (2)
ans = (2) – (1)
ans = log(a1/a2) + b1 – b2Therefore: int ans = log(a1/a2) + b1 – b2
- if a1 < 0, then ans = -ans. This is because both a1 and a2 are both negative.
- if ans < 0, print N.
- else if ans > 0, print M.
- else print Equal.
Below is the Java program to implement the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to extract mantissavector<int> extract_mantissa(string N,string M){ vector<int> mantissa(2); int mulInd1; for(int i=0;i<N.size();i++) { if(N[i]=='*') { mulInd1=i; break; } } int a1 = stoi(N.substr(0, mulInd1)); mantissa[0] = a1; int mulInd2; for(int i=0;i<M.size();i++) { if(M[i]=='*') { mulInd2=i; break; } } int a2 = stoi(M.substr(0, mulInd2)); mantissa[1] = a2; return mantissa;} // Function to extract exponentvector<int> extract_exponent(string N,string M){ vector<int> exponent(2); int powInd1; for(int i=0;i<N.size();i++) { if(N[i]=='^') { powInd1=i; break; } } int b1 = stoi(N.substr(powInd1 + 1)); exponent[0] = b1; int powInd2; for(int i=0;i<M.size();i++) { if(M[i]=='^') { powInd2=i; break; } } int b2 = stoi(M.substr(powInd2 + 1)); exponent[1] = b2; return exponent;} // Function to find smaller numbervoid solution(int a1, int b1, int a2, int b2){ double x = ((double)(a1) / (double)(a2)); double ans = (b1 - b2 + log10(x)); // If both are negative if(a1 < 0) ans = -ans; if(ans < 0) cout << "N\n"; else if(ans > 0) cout << "M\n"; else cout << "Equal\n";} void solve(string N, string M){ // Extract mantissa(a1) and mantissa(a2) // from num1 and num2 vector<int> mantissa = extract_mantissa(N, M); // Extract exponent(b1) and exponent(b2) // from num1 and num2 vector<int> exponent = extract_exponent(N, M); if(mantissa[0] > 0 && mantissa[1] < 0) cout << "M\n"; else if(mantissa[0] < 0 && mantissa[1] > 0) cout << "N\n"; else { // if mantissa of both num1 and num2 // are positive or both are negative solution(mantissa[0], exponent[0], mantissa[1], exponent[1]); }} // Driver codeint main (){ // Mantissa is negative and // exponent is positive string N = "-5*10^3"; string M = "-50*10^2"; solve(N, M); // Mantissa is negative and // exponent is negative N = "-5*10^-3"; M = "-50*10^-2"; solve(N, M); // Mantissa is positive and // exponent is negative N = "5*10^-3"; M = "50*10^-2"; solve(N, M); // Mantissa is positive and // exponent is positive N = "5*10^3"; M = "50*10^2"; solve(N, M); return 0;}//This code is contributed by adityapatil12 |
Java
// Java program to implement // the above approachimport java.io.*;import java.util.*;import java.math.*;import java.lang.*;class GFG { // Function to extract mantissa static int[] extract_mantissa(String N, String M) { int mantissa[] = new int [2]; int mulInd1 = N.indexOf('*'); int a1 = Integer.parseInt( N.substring(0, mulInd1)); mantissa[0] = a1; int mulInd2 = M.indexOf('*'); int a2 = Integer.parseInt( M.substring(0, mulInd2)); mantissa[1] = a2; return mantissa; } // Function to extract exponent static int[] extract_exponent(String N, String M) { int exponent[] = new int [2]; int powInd1 = N.indexOf('^'); int b1 = Integer.parseInt( N.substring(powInd1 + 1)); exponent[0] = b1; int powInd2 = M.indexOf('^'); int b2 = Integer.parseInt( M.substring(powInd2 + 1)); exponent[1] = b2; return exponent; } // Function to find smaller number static void solution(int a1, int b1, int a2, int b2) { double x = ((double)(a1) / (double)(a2)); double ans = (b1 - b2 + Math.log10(x)); // If both are negative if(a1 < 0) ans = -ans; if(ans < 0) System.out.println("N"); else if(ans > 0) System.out.println("M"); else System.out.println("Equal"); } static void solve(String N, String M) { // Extract mantissa(a1) and mantissa(a2) // from num1 and num2 int mantissa[] = extract_mantissa(N, M); // Extract exponent(b1) and exponent(b2) // from num1 and num2 int exponent[] = extract_exponent(N, M); if(mantissa[0] > 0 && mantissa[1] < 0) System.out.println("M"); else if(mantissa[0] < 0 && mantissa[1] > 0) System.out.println("N"); else { // if mantissa of both num1 and num2 // are positive or both are negative solution(mantissa[0], exponent[0], mantissa[1], exponent[1]); } } // Driver code public static void main (String[] args) { // Mantissa is negative and // exponent is positive String N = "-5*10^3"; String M = "-50*10^2"; solve(N, M); // Mantissa is negative and // exponent is negative N = "-5*10^-3"; M = "-50*10^-2"; solve(N, M); // Mantissa is positive and // exponent is negative N = "5*10^-3"; M = "50*10^-2"; solve(N, M); // Mantissa is positive and // exponent is positive N = "5*10^3"; M = "50*10^2"; solve(N, M); }} |
Python3
# Python 3 program to implement# the above approachimport math# Function to extract mantissadef extract_mantissa(N, M): mantissa = [0]*2 mulInd1 = list(N).index('*') a1 = N[0: mulInd1] mantissa[0] = a1 mulInd2 = list(M).index('*') a2 = M[0: mulInd2] mantissa[1] = a2 return mantissa# Function to extract exponentdef extract_exponent(N, M): exponent = [0]*2 powInd1 = list(N).index('^') b1 = N[powInd1 + 1:] exponent[0] = b1 powInd2 = list(M).index('^') b2 = M[powInd2 + 1:] exponent[1] = b2 return exponent# Function to find smaller numberdef solution(a1, b1, a2, b2): x = int(a1) / int(a2) ans = (int(b1) - int(b2) + math.log10(x)) # If both are negative if(int(a1) < 0): ans = -ans if(ans < 0): print("N") elif(ans > 0): print("M") else: print("Equal")def solve(N, M): # Extract mantissa(a1) and mantissa(a2) # from num1 and num2 mantissa = extract_mantissa(N, M) # Extract exponent(b1) and exponent(b2) # from num1 and num2 exponent = extract_exponent(N, M) if(int(mantissa[0]) > 0 and int(mantissa[1]) < 0): print("M") elif(int(mantissa[0]) < 0 and int(mantissa[1]) > 0): print("N") else: # if mantissa of both num1 and num2 # are positive or both are negative solution(mantissa[0], exponent[0], mantissa[1], exponent[1])# Driver codeif __name__ == "__main__": # Mantissa is negative and # exponent is positive N = "-5*10^3" M = "-50*10^2" solve(N, M) # Mantissa is negative and # exponent is negative N = "-5*10^-3" M = "-50*10^-2" solve(N, M) # Mantissa is positive and # exponent is negative N = "5*10^-3" M = "50*10^-2" solve(N, M) # Mantissa is positive and # exponent is positive N = "5*10^3" M = "50*10^2" solve(N, M) # This code is contributed by ukasp. |
C#
// C# program to implement // the above approachusing System;class GFG { // Function to extract mantissa public static int[] extract_mantissa(String N, String M) { int[] mantissa = new int [2]; int mulInd1 = N.IndexOf('*'); int a1 = int.Parse(N.Substring(0, mulInd1)); mantissa[0] = a1; int mulInd2 = M.IndexOf('*'); int a2 = int.Parse(M.Substring(0, mulInd2)); mantissa[1] = a2; return mantissa; } // Function to extract exponent public static int[] extract_exponent(String N, String M) { int[] exponent = new int [2]; int powInd1 = N.IndexOf('^'); int b1 = int.Parse(N.Substring(powInd1 + 1)); exponent[0] = b1; int powInd2 = M.IndexOf('^'); int b2 = int.Parse( M.Substring(powInd2 + 1)); exponent[1] = b2; return exponent; } // Function to find smaller number static void solution(int a1, int b1, int a2, int b2) { double x = ((double)(a1) / (double)(a2)); double ans = (b1 - b2 + Math.Log10(x)); // If both are negative if(a1 < 0) ans = -ans; if(ans < 0) Console.WriteLine("N"); else if(ans > 0) Console.WriteLine("M"); else Console.WriteLine("Equal"); } static void solve(String N, String M) { // Extract mantissa(a1) and mantissa(a2) // from num1 and num2 int[] mantissa = extract_mantissa(N, M); // Extract exponent(b1) and exponent(b2) // from num1 and num2 int[] exponent = extract_exponent(N, M); if(mantissa[0] > 0 && mantissa[1] < 0) Console.WriteLine("M"); else if(mantissa[0] < 0 && mantissa[1] > 0) Console.WriteLine("N"); else { // if mantissa of both num1 and num2 // are positive or both are negative solution(mantissa[0], exponent[0], mantissa[1], exponent[1]); } } // Driver code public static void Main () { // Mantissa is negative and // exponent is positive String N = "-5*10^3"; String M = "-50*10^2"; solve(N, M); // Mantissa is negative and // exponent is negative N = "-5*10^-3"; M = "-50*10^-2"; solve(N, M); // Mantissa is positive and // exponent is negative N = "5*10^-3"; M = "50*10^-2"; solve(N, M); // Mantissa is positive and // exponent is positive N = "5*10^3"; M = "50*10^2"; solve(N, M); }}// This code is contributed by saurabh_jaiswal. |
Javascript
// JavaScript program to implement// the above approach// Function to extract mantissafunction extract_mantissa(N, M){ var mantissa = new Array(2); var mulInd1 = N.indexOf('*'); var a1 = parseInt(N.substring(0, mulInd1)); mantissa[0] = a1; var mulInd2 = M.indexOf('*'); var a2 = parseInt(M.substring(0, mulInd2)); mantissa[1] = a2; return mantissa;}// Function to extract exponentfunction extract_exponent(N, M){ var exponent = new Array(2); var powInd1 = N.indexOf('^'); var b1 = parseInt(N.substring(powInd1 + 1)); exponent[0] = b1; var powInd2 = M.indexOf('^'); var b2 = parseInt(M.substring(powInd2 + 1)); exponent[1] = b2; return exponent;}// Function to find smaller numberfunction solution(a1, b1, a2, b2){ var x = parseFloat(a1) / parseFloat(a2); var ans = (b1 - b2 + Math.log10(x)); // If both are negative if(a1 < 0) ans = -ans; if(ans < 0) console.log("N" + "<br>"); else if(ans > 0) console.log("M" + "<br>"); else console.log("Equal" + "<br>");}function solve(N, M){ // Extract mantissa(a1) and mantissa(a2) // from num1 and num2 var mantissa = extract_mantissa(N, M); // Extract exponent(b1) and exponent(b2) // from num1 and num2 var exponent = extract_exponent(N, M); if(mantissa[0] > 0 && mantissa[1] < 0){ console.log("M" + "<br>"); } else if(mantissa[0] < 0 && mantissa[1] > 0){ console.log("N" + "<br>"); } else{ // if mantissa of both num1 and num2 // are positive or both are negative solution(mantissa[0], exponent[0], mantissa[1], exponent[1]); }}// Mantissa is negative and// exponent is positivevar N = "-5*10^3";var M = "-50*10^2";solve(N, M);// Mantissa is negative and// exponent is negativeN = "-5*10^-3";M = "-50*10^-2";solve(N, M);// Mantissa is positive and// exponent is negativeN = "5*10^-3";M = "50*10^-2";solve(N, M);// Mantissa is positive and// exponent is positiveN = "5*10^3";M = "50*10^2";solve(N, M);// This code is contributed by lokesh. |
Output:
Equal
M
N
Equal
Time Complexity: O ( 1 )
According to the given constraints |a| can be of a maximum of 10 lengths of string and if it is negative, then it could be of 11 lengths, similarly b can also be of 11 digits. The maximum length of string could be 25 (11 +3+11), so we can consider extracting a and b of constant time operation.
Auxiliary Space: O ( 1 )
