Task and Solution : Other Concepts Bit Array of HackerRank

 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.

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 */  

    unsigned int N, S, P, Q, mod, prev;

   

    cin >> N >> S >> P >> Q;

   

    mod = pow(2, 31);

    prev = S;

    int numDistinct = 1;

     

    for (int i = 1; i < N; i++) {

        S = (S * P + Q) % mod;

        numDistinct += (S != prev) ? 1 : 0;

        prev = S;

    }

   

    cout << numDistinct;

   

    return 0;

}

Source : HackerRank