time issue with my C code on bitwise operator. Please tell me some changes so that my C code becomes efficient to run in minimum time

Question

My code for this problem fails due to the time limit:

• Given integers n and k as space-separated numerals in the standard input stream, print on separate lines the maximum value of { a AND b | 0 < a < b ≤ n, a AND b < k }, the maximum value of { a OR b | 0 < a < b ≤ n, a OR b < k }, and the maximum value of { a XOR b | 0 < a < b ≤ n, a XOR b < k }.

Sample Input

5 4

Sample Output

2
3
3

This is the code I tried

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
//Complete the following function.

void sort(int temp,int arr[]){
    int t=0;
    for (int i = 0; i < temp; i++) { 
        for (int j = i + 1; j < temp; j++) { 
            if (arr[i] < arr[j]) { 
                t = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = t; 
            } 
        } 
    }
}
void calculate_the_maximum(int n, int k) {
    int array_size = 0;
    int temp = n-1;
    while(temp!=0){
        array_size += temp;
        temp--;
    }
    temp = 0;
    int and[array_size];
    int or[array_size];
    int xor[array_size];
    int minand = 0;
    int minor = 0;
    int minxor = 0;
    for (int a =1; a <= (n-1); a++){
        for (int b = a+1; b <= n; b++){
            and[temp] = a&b;
            or[temp] = a|b;
            xor[temp] = a^b;
            temp += 1;
        }
    }
    sort(temp,and);
    sort(temp,or);
    sort(temp,xor);
    for(int i = 0;i<temp;i++){
        if(and[i]<k){
            minand = and[i];
            break;
        }
    }
    for(int i = 0;i<temp;i++){
        if(or[i]<k){
            minor = or[i];
            break;
        }
    }
    for(int i = 0;i<temp;i++){
        if(xor[i]<k){
            minxor = xor[i];
            break;
        }
    }
    printf("%d\n",minand);
    printf("%d\n",minor);
    printf("%d\n",minxor);
}

int main() {
    int n, k;
  
    scanf("%d %d", &n, &k);
    calculate_the_maximum(n, k);
 
    return 0;
}

The code executes successfuly but four out of 13 test cases fail due to time limits. Is there any another way to solve the problem which takes less time to execute?

Answer 1

To improve the time efficiency, you can optimize the algorithm. Instead of generating all pairs and then calculating the bitwise operations, you can directly calculate the results without the need for nested loops.

void calculate_the_maximum(int n, int k) {
    int maxAnd = 0;
    int maxOr = 0;
    int maxXor = 0;

    for (int a = 1; a <= n - 1; a++) {
        for (int b = a + 1; b <= n; b++) {
            int currentAnd = a & b;
            int currentOr = a | b;
            int currentXor = a ^ b;

            if (currentAnd < k && currentAnd > maxAnd) {
                maxAnd = currentAnd;
            }
            if (currentOr < k && currentOr > maxOr) {
                maxOr = currentOr;
            }
            if (currentXor < k && currentXor > maxXor) {
                maxXor = currentXor;
            }
        }
    }

    printf("%d\n%d\n%d\n", maxAnd, maxOr, maxXor);
}