Bit Array in C++ HackerRank Solution

Hello Programmers, In this post, you will know how to solve the Bit Array in C++ HackerRank Solution. This problem is a part of the HackerRank C++ Programming Series.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Bit Array in C++ HackerRank Solutions

report this adObjective

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++ HackerRank Solutions

#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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: C++ Class Template Specialization in C++ HackerRank Solution