c++exponenterror-correction

My code to find all pairs of numbers such that x^y > y^x producing the wrong output


The problem is: given two arrays of positive integers of lengths m and n find all pairs of (x, y) such that x^y > y^x. (Raising the left operand to the power of the right)

I have followed the following logic:

  1. if x = 1 then no ordered pairs satisfies the conditions.

  2. if y = 1 and x != 1, the condition is satisfied for all x.

  3. the condition is true for all remaining cases where y > x.

  4. Exceptions are : (2, 3), (2, 4) and (3, 2)

My code is:

    int main(){
        int n, m;
        cin >> m >> n;
        int a[m], b[n];
        for(int i = 0; i < m; i++) cin >> a[i];
        for(int i = 0; i < n; i++) cin >> b[i];
        int count = 0;
        for(int i = 0; i < m; i++){
            if(a[i] != 1){  
                for(int j = 0; j < n; j++){
                    if(b[j] == 1) count++;
                    else if(a[i] == 2 && b[j] >= 5) count++;
                    else if(a[i] == 3 &&(b[j] == 2 || b[j] >=4)) count++;
                    else if(b[j] > a[i]) count++;
                }
            }
        }
        cout << count << endl;
    }

For certain large outputs (on geeksforgeeks) the code outputs a value of one more than the correct answer. (e.g., 12575 instead of the expected output of 12574, an error of 1)

I am unable to figure out where the code fails. Thanks for the help!


Solution

  • You're counting both (2, 4) and (2, 3), since those cases end up in the last condition.

    The simplest way to treat them as exceptions is to make sure that you handle all "2 cases" at once:

    if (a[i] == 2) 
        if (b[j] >= 5) 
             count++;
    

    or

    if (a[i] == 2) 
        count += b[j] >= 5;
    

    When your code is supposed to make exceptions for certain cases, make sure that you test those exceptional cases.