Bit Array in C++ - Hacker Rank Solution
Problem
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^8
0 <= 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.
Solution :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | //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; } |
the above hole problem statement is given by hackerrank.com but the solution is generated by the codeworld19 authority if any of the query regarding this post or website fill the following contact form thank you.
CodeWorld19
Hey, I am Parthe Omkar