Google SWE Online Coding Challenge Internship 2021

✔️ First Question: The maximum XOR value

Given an array of N Integers.

You are given q queries. Each query has 2 integers x and m.

For each query, you are required to determine the array value that provides the maximum bitwise XOR value with x where the array value is not more than m.

If there is no such value that satisfies then condition, then print -1.

 

Input Format

A first line is a number of test cases T.

Each test case contain an integer N denoting the number of elements in the array.

The second line of each test case contains array elements.

The third line denoted the number of queries q. Next q lines contain two integers x and m.

 

Example

Input	Output
1 7 3 7 19 18 7 12 17 7 3 8 21 20 24 17 1 7 23 17 12 9	7 12 7 7 12 3 -1

 

 

🎈 Question

양의 정수로 이루어진 list와 query(X, M)가 주어질때, M보다 크지 않으면서 X와의 XOR 연산 값이 가장 큰 수를 list에서 찾아 반환하면 된다.

예시에서는 query의 개수가 7개인데 6개밖에 주어지지 않았길래 뭐지? 싶었는데 그냥 없는 쿼리인 것이다. 

그래서 Output에서도 제일 마지막에는 값을 찾을 수 없다는 뜻으로 -1을 출력하고 있다. 

 

 

🎈 Solution

list와 query를 입력받고 list는 오름차순 정렬을 한다.(연산 횟수 줄이기 위해)

<string> 헤더의 upper_bound 함수를 사용하여 M보다 작거나 같은 값을 가지는 list의 인덱스를 찾는다.

그리고 for문을 통해 해당 인덱스까지만 돌면서 X와 XOR 연산을 하고 그 중 최댓값을 찾아 ans 배열에 삽입한다.

마지막으로 ans 배열을 출력하면 끝!

그런데 문제의 예시와 같이 query문을 부족하게 입력한 경우는 어떻게 해야할지 몰라서 구현하지 못했다.

누가 좀 알려주세요,,,

 

🎈 Time Complexity

main에서 for문 실행할때마다 maxXOR 함수의 for문이 실행되므로 O(n^2)

 

🎈 Space Complexity

maxXOR의 for문에서 ans 배열의 크기가 계속 증가하므로 O(n)

 

🎈 Code(C++)

// Google SWE Online Coding Challenge Internship 2021
// https://www.geeksforgeeks.org/gocc15-google-swe-online-coding-challenge-internship-2021/?ref=rp
// The maximum XOR value

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void maxXOR(int, int);
vector <int> arr, ans;

int main(void)
{
    int t, n, q, tmp, x, m;
    cin >> t; // test cases
    while(t--) {
        cin >> n; // the number of elements in the array
        for(int i = 0 ; i < n ; i++) {
            cin >> tmp;
            arr.push_back(tmp); 
        }
        
        sort(arr.begin(), arr.end()); // 오름차순 정렬

        cin >> q; //  the number of queries
        for(int i = 0 ; i < q ; i++) {
            cin >> x >> m;
            maxXOR(x, m);
        }
    }

    // 정답 출력
    for(int i = 0 ; i < q ; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

/*
    determine the array value that provides the maximum bitwise XOR value with x 
    where the array value is not more than m
*/
void maxXOR(int x, int m)
{
    int max = 0, idx = -1;

    // it = M보다 작거나 같은 값을 갖는 arr 원소 인덱스 
    int it = upper_bound(arr.begin(), arr.end(), m) - arr.begin() - 1;
    if(it < 0) { // 조건 만족하는 값 없는 경우
        ans.push_back(-1);
        return;
    }

    for(int j = 0 ; j < it ; j++) {
        if(max < (x ^ arr[j])) {
            max = (x ^ arr[j]);
            idx = j;
        }
    }
    ans.push_back(arr[idx]);
}