Google online challenge 2020 for summer internships

✔️ Second Question: Given a list which initially contains 0, the following queries can be performed:

 

• 0 X: add X to the list
• 1 X: replace each element “A” of the list by A^X, where ^ is the xor operator

Return a list with the result elements in increasing order.

문제 링크

Google Online Challenge 2020 - GeeksforGeeks

 

 

🎈 Question

0만 있는 초기 배열이 있을 때

주어지는 query문에 따라 배열의 원소를 계산하는 문제이다.

query문의 종류는 크게 두 가지이다.

0 X: 원소 X를 배열에 추가
1 X: 배열의 각 원소를 X와 XOR 연산한 결과로 치환

 

Input	Output
3 0 2 1 3 0 5	1 3 5

 

Input	Output
5 0 4 0 2 1 4 0 5 1 8	8 12 13 14

 

 

🎈 Solution

예를 들어, query가 {0, 2}, {1, 3}, {0, 5} 와 같이 주어졌다면

초기 리스트: list = [0]

1) {0, 2}

원소 2를 배열에 추가해야 하므로

list = [0, 2]

2) {1, 3}

배열의 각 원소를 3과 XOR 연산한 결과로 치환해야 한다.

0 XOR 3 = 3

2 XOR 3 = 1

list = [3, 1]

3) {0, 5}

원소 5를 배열에 추가해야 하므로

list = [3, 1, 5] 

 

최종 답은 오름차순으로 정렬한 결과를 출력하면 되므로

list = [1, 3, 5]

 

 

🎈 Time Complexity

1) Best

: qeury가 모두 { 0 X } 꼴인 경우

두 번째 for문이 실행되지 않으므로 

시간복잡도는 O(n)

2) Worst

: query가 { 0 X }, { 1 X } 꼴이 번갈아 나오는 경우

시간복잡도는 O(n^2)

3) 평균

두 번째 반복문이 list.size 만큼 반복되므로

시간복잡도는 O(n*list.size)

 

 

🎈 Space Complexity

query에 따라 list 배열이 가변적이므로

공간복잡도는 O(n)

 

 

🎈 Code(C++)

// Google online challenge 2020 for summer internships 2021
// https://www.geeksforgeeks.org/google-online-challenge-2020/
// Construct a List using the given Q XOR queries

#include <cstdio>
#include <vector>
#include <algorithm> 
#define MAX 1000

using namespace std;

int main(void)
{
    int queryNum;
    int queries[MAX][MAX];
    vector<int> list;
    scanf("%d", &queryNum);
    
    list.push_back(0); // initial list

    for(int i = 0 ; i < queryNum ; i++) {
        scanf("%d %d", &queries[i][0], &queries[i][1]);
        if(queries[i][0] == 0) { // add element to list
            list.push_back(queries[i][1]);
        }
        else { // replace each element “A” of the list by A^X(XOR)
            for(int j = 0 ; j < list.size() ; j++) {
                list[j] = (list[j] ^ queries[i][1]); 
            }
        }
    }

    sort(list.begin(), list.end()); // 오름차순 정렬
    for(int i = 0 ; i < list.size() ; i++) {
        printf("%d ", list[i]);
    }

    return 0;
}