Bit Array in C++ – Hacker Rank Solution

Bit Array in C++ - Hacker Rank Solution
Bit Array in C++ – Hacker Rank Solution

Objective

You are given four integers: N, S, P, Q. You will use them in order to create the sequence a 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^80 <= S,P,Q <= 2^31


Sample Input :

3 1 1 1

Sample Output :

3

Explanation :

a = [1,2,3]
Hence, there are  3 different integers in the sequence.



Bit Array in C++ – Hacker Rank Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    /* Bit Array in C++ - Hacker Rank Solution */
    uint_fast64_t po = (uint_fast64_t)(pow(2, 31));
    uint_fast64_t N, S, P, Q;
    cin >> N >> S >> P >> Q;
    bool r = false;
    uint_fast64_t c = 0;
    uint_fast64_t prv = S % po;
    uint_fast64_t crn = -1;
    uint_fast64_t i = 1;
    do
    {
        crn = (prv * P + Q) % po;
        if (crn != prv)
        {
            prv = crn;
            ++c;
        }
        else
        {
            r = true;
        }
        ++i;
    } while (i < N && !r);
    cout << c + 1 << endl;
    /* Bit Array in C++ - Hacker Rank Solution */
    return 0;
}

Disclaimer: The above Problem (Bit Array in C++ ) is generated by Hackerrank but the Solution is Provided by Chase2Learn. This tutorial is only for Educational and Learning purposes. Authority if any of the queries regarding this post or website fill the following contact form thank you.

Leave a Comment