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