HackerRank Bit Array(Hard) 문제풀이

문제

You are given four integers: N, S, P, Q. You will use them in order to create the sequence  with the following pseudo-code.

a[0] = S (modulo 2^31)
for i = 1 to N-1
    a[i] = a[i-1]*P+Q (modulo 2^31)

Your task is to calculate the number of distinct integers in the sequence a.

 

Input Format

Four space separated integers on a single line, N, S, P, and Q respectively.

 

Output Format

A single integer that denotes the number of distinct integers in the sequence a.

 

Constraints

1<= N <= 10^8

0 <= S, P, Q <= 2^31

 

Sample Input

3 1 1 1

 

Sample Output

3

 

해설

 계속해서 증가하는 숫자가 오버플로 되며 0~2^31 구간을 최대 10^8만큼 반복할 때, 큼 반복되기 전까지의 숫자 가짓수를 구하는 문제다. 머릿속에 가장 빠르게 떠오르는 방법은 숫자를 set에 저장하고 중복된 값이 들어오면 set의 길이를 출력하는 것이다. 하지만 문제는 set에 값을 추가할 때마다 드는 시간이다.

 set보다 빠른 unordered_set도 O(1)의 평균 시간 복잡도로 삽입 및 검색을 수행하는데 이 문제는 이마저도 허락하지 않는다. 하지만 vector를 사용해 미리 배열 크기를 확보하고 push_back을 사용하는 것은 가능했다.

 숫자가 증가하는 공식은 a[i] = (a[i-1]*P+Q) 이다. 하지만 a[i]가 2^31이 넘어버린다면 오버플로가 발생하기 때문에 a[i] = a[i-1]*P+Q%2^31 이 올바른 수식이다. 여기까지 이해하면 아래와 같은 코드를 만들 수 있다.

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

int main() {
    int N, S, P, Q;
    int mod = 1 << 31;
    cin >> N >> S >> P >> Q;

    vector<int> a(N + 1);
    a[0] = S % mod;
    
    //todo
    
    return 0;
}

 

여기서 이 문제의 핵심은 a[0] -> a[1] -> a[2] -> a[3] 로 점차 증가할 때, 어느 순간 오버플로가 발생해 a[n] == a[i] (i<n)가 되는 순간을 포착해야 하는 것이다. 즉, 플로이드의 순환 알고리즘을 알아야 한다.

https://fierycoding.tistory.com/45

플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) / 증명 / leetcode 287번 / 파이썬

비교하는 두 포인터가 서로 한 칸씩 멀어지면서 두 값을 비교하고, 두 값이 같아지는 순간 거북이에 해당하는 포인터의 위치까지가 유니크한 값이고, 그 이후부터는 반복되는 구간인 것이다. 즉, 모든 값을 중복 확인하거나 자료구조에 넣어 저장할 필요가 없다.

 

정답코드

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

int main() {
    int N, S, P, Q;
    int mod = 1 << 31;
    cin >> N >> S >> P >> Q;

    vector<int> a(N + 1);
    a[0] = S % mod;
    int ih = 0, it = 1;

    while (it < N) {
        ih += 2;

        if (ih <= N) {
            a[ih - 1] = (a[ih - 2] * P + Q) % mod;
            a[ih] = (a[ih - 1] * P + Q) % mod;

            if (a[ih] == a[it++]) break;
        }
        else {
            it = N + 1;
            break;
        }
    }

    cout << it - 1;
    
    return 0;
}