dificilcoder's blog

Hard Compare — Exponential
By dificilcoder, history, 4 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Take log both the sides and compare

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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}$$$

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but why the pow function doesn't work on that question??

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can't use modulo before comparison.

          1 % (1e9 + 7) = 1
          (1e9 + 7) % (1e9 + 7) = 0

          but 1 isn't greater than 1e9 + 7.

          → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        log functions will give you float values. Isn't it bad practice to compare floats?

        → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use 128-bit integers.

→ Reply