# HackerRank Bit Array solution in c++ programming

In this HackerRank Bit Array problem solution in the c++ programming language, You are given four integers: N, S, P, Q. You will use them in order to create the sequence with the following pseudo-code. Your task is to calculate the number of distinct integers in sequence a.

## HackerRank Bit Array problem solution in c++ programming.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;

int main() {
unsigned long long n,s,p,q,r=0,ans=0,returned,v;
n=100000000; s=1232077670; p=126810854; q=1536183938; //26
// n=100000000; s=569099406; p=1607140150; q=823906344; //31
cin>>n>>s>>p>>q;
unsigned long long i, a0=s, a=s, ap=0, k=0, kt=0;

v=pow(2,31);
// v-=1;
// cout<<bitset<64>(v)<<endl;
// v=~v;
// cout<<bitset<64>(v)<<endl;
for(i=0; i<n; i++){
// a=(a*p+q)&v;
a=(a*p+q);
a=a%v;
// cout<<bitset<64>(a)<<" 1 "<<endl;
// a&=v;
// cout<<bitset<64>(a)<<endl;
if((a==a0 || a==ap) && i!=0){
k=i+1;
break;
}
ap=a;
}
if (i==n) k=i;

cout <<k<<endl;

return 0;
}```

## Second solution

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

unsigned insert(unsigned x) {
unsigned res = (mask[x >> 6] & (1ULL << (x & 0x3F))) == 0;
mask[x >> 6] |= 1ULL << (x & 0x3F);
return res;
}

int main() {
unsigned N, S, P, Q;
cin >> N >> S >> P >> Q;
unsigned x = S;
unsigned ans = 0;
ans += insert(x);
for (unsigned i = 1; i < N; i++) {
x = (1LL * x * P + Q) % 2147483648;
ans += insert(x);
}
cout << ans << endl;
return 0;
}```

### Third solution

```#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <bitset>
#include <iostream>

#define pb push_back
#define all(x) (x).begin(), (x).end()

#ifdef KAZAR
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
#define eprintf(...) 0
#endif

using namespace std;

template<class T> inline void umax(T &a,T b){if(a < b) a = b;}
template<class T> inline void umin(T &a,T b){if(a > b) a = b;}
template<class T> inline T abs(T a){return a > 0 ? a : -a;}

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int inf = 1e9 + 143;
const ll longinf = 1e18 + 143;

inline int read(){int x;scanf(" %d",&x);return x;}

const unsigned M = (1ll << 31) - 1;
const int MAX = 1 << 26;
const int K = 16;
const int MSK = (1 << K) - 1;

int kb[1 << K];
unsigned f[MAX];

int main(){

#ifdef KAZAR
freopen("f.input","r",stdin);
freopen("f.output","w",stdout);
freopen("error","w",stderr);
#endif

unsigned s, p, q;
cin >> s >> p >> q;

f[s >> 5] |= 1u << (s & 31);
for (int i = 1; i < n; i++) {
s = (s * p + q) & M;
f[s >> 5] |= 1u << (s & 31);
}

for (int i = 0; i < (1 << K); i++) {
kb[i] = kb[i >> 1] + (i & 1);
}

int res = 0;
for (int i = 0; i < MAX; i++) {
res += kb[f[i] >> 16] + kb[f[i] & MSK];
}
printf("%d\n", res);

return 0;
}```