How to arrive at the correct solution which solves for large input values?
Problem : Hard Compare...
Question
Given 4 numbers A,B,C and D. If AB > CD, print "YES" otherwise, print "NO".
Input
Only one line containing 4 numbers A,B,C and D (1≤A,C≤107) , (1≤B,D≤1012)
Output
Print "YES" or "NO" according to the problem above.
My Program
#include <iostream>
#define ll long long
using namespace std;
int main(){
ll res1, res2, a, b, c, d;
cin>>a>>b>>c>>d;
res1 = 1;
res2 = 1;
for(int i=1;i<=b; i++){
res1 = a % ((int)1e9+7) * res1 % ((int)1e9+7);
}
for(int i=1;i<=d; i++){
res2 = c % ((int)1e9+7) * res2 % ((int)1e9+7);
}
cout<<(res1>res2 ? "YES" : "NO");
return 0;
}
TestCases
Input : 2887969 614604076030 8478041 209676100616
Answer : YES
Input : 8376260 70 8376259 70
Answer : YES
Input : 2 1 1 1
Answer : YES
Input : 1 7816997 1 1
Answer : NO
Issue with current program : I am not able to solve for large input values
Take log both the sides and compare
how?
Since $$$A, B, C, D > 1$$$
We have $$$AB > CD \Leftrightarrow log_k(AB) > log_k(CD)$$$ for $$$k > 1$$$
You can also try $$$\frac{A}{C} > \frac{D}{B}$$$
but why the pow function doesn't work on that question??
You can't use modulo before comparison.
1 % (1e9 + 7) = 1
(1e9 + 7) % (1e9 + 7) = 0
but 1 isn't greater than 1e9 + 7.
The exponents are too big to store the results in long long int, so we need to change the approach. We need only to know what is greater, no the values.
log functions will give you float values. Isn't it bad practice to compare floats?
You can use 128-bit integers.