Bit Array HackerRank Solution in C++

Bit Array HackerRank Solution in C++

In this Bit Array in C++ HackerRank solution, You are given four integers: . 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 .

Input Format

Four space separated integers on a single line, , , , and  respectively.

Output Format

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

Constraints


Sample Input

3 1 1 1

Sample Output

3

Explanation

Hence, there are  different integers in the sequence.

Bit Array HackerRank Solution in C++

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in C++

int main() {
    uint32_t N,S,P,Q;
    cin>>N>>S>>P>>Q;
    uint32_t prev;
    int count=1;
    vector<bool> presence(1u << 31, false);
    prev= S%(1u<<31);
    presence[prev]=true;
    for (int i=1;i<N;i++)
    {
        prev=(prev*P+Q)%(1u<<31);
        if (!presence[prev]) {
            presence[prev] = true;
            count++;
        }
    }
    cout<<count;
    return 0;
}
Solve original Problem on HackerRank here. Checkout more HackerRank Problems