We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
3 cases for N = 1 and 2:
* a return 1
* a,a return 1 - this is valid for all values of N
* a,d return 2
In most cases at some point we get a value which already exists, means that a cycle is starting or repeated values and we can stop checking. There are 3 cases:
1) cycle starts from first item
stop when itemCurr == itemOne / S /
1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5, ...
1,2,3,4,5|1,2,3,4,5|1,2,3,4,5|1,2,3,4,5|
2) cycle starts from second item stop when itemCurr == itemTwo
1,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5, ...
2,3,4,5|2,3,4,5|2,3,4,5|2,3,4,5|
3) repeating item starts from somewhere stop when itemCurr == itemPrev
1,2,3,4,5,6,7,8,9,10,10,10,10,10,10,10, ...
10,10,10,10,10,10,10,
If we reach the end without finding repeating item:
unique numbers to N-count --> N
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,...
and the code:
long long itemTwo = (S * P + Q) & mask; // auto mask = ((1ll << 31) - 1ll);
if ( N == 1 || S == itemTwo ) return 1;
if ( N == 2 ) return 2;
long long itemPrev = itemTwo, itemCurr, i = 3; // i is not zero index but in 1 to N
for ( ; i <= N; i++ ) {
itemCurr = (itemPrev * P + Q) & mask;
if ( itemCurr == itemTwo || itemCurr == S || itemCurr == itemPrev ) {
return i - 1;
}
itemPrev = itemCurr;
}
return N;
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Bit Array
You are viewing a single comment's thread. Return to all comments →
3 cases for N = 1 and 2: * a return 1 * a,a return 1 - this is valid for all values of N * a,d return 2
In most cases at some point we get a value which already exists, means that a cycle is starting or repeated values and we can stop checking. There are 3 cases:
1) cycle starts from first item stop when itemCurr == itemOne / S / 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5, ... 1,2,3,4,5|1,2,3,4,5|1,2,3,4,5|1,2,3,4,5|
2) cycle starts from second item
stop when itemCurr == itemTwo 1,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5, ... 2,3,4,5|2,3,4,5|2,3,4,5|2,3,4,5|
3) repeating item starts from somewhere
stop when itemCurr == itemPrev 1,2,3,4,5,6,7,8,9,10,10,10,10,10,10,10, ... 10,10,10,10,10,10,10,
If we reach the end without finding repeating item:
unique numbers to N-count --> N 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,...
and the code: