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.
  1. Prepare
  2. C++
  3. Other Concepts
  4. Bit Array
  5. Discussions

Bit Array

Sort by

recency

|

315 Discussions

|

  • zyncgames
     + 0 comments

    I think like most people, I simply started to program, leading me to a simple interpretation of the pseudo-code that used a set to track distinct integers; of course that implementation didn't pass any of the timed test cases.

    In the end, this problem is not about c++, but an understanding of algorithms. After research, I stumbled across the idea of cycle detection https://en.wikipedia.org/wiki/Cycle_detection, and tried out the first algorithm listed.

    I know many people don't like it when code is shared since it kind of defeats the “test” notion, but when I get stuck, I personally am thankful for those who post so I can treat the question as a learning exercise (I spent more time researching this than coding this one):

    #include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

const unsigned bit_mask = ((1U << 31) - 1);

inline unsigned mask(unsigned num) {
    return num & bit_mask;
}

inline unsigned next_value(unsigned value, unsigned P, unsigned Q) {
    return mask(value * P + Q);
}

int main() {
    // Get the 4 input integers as unsigned ints
    unsigned N, S, P, Q; cin >> N >> S >> P >> Q;
    
    // Used Floyd's tortoise and hare cycle-finding algorithm:
    //  https://en.wikipedia.org/wiki/Cycle_detection
    unsigned tort = mask(S);
    unsigned hare = tort;
    unsigned cycle = 1;
    
    // Calculate the length of a cycle (if one exists) or stop at N
    for (unsigned i = 1; i < N; i++) {
        tort = next_value(tort, P, Q);
        hare = next_value(next_value(hare, P, Q), P, Q);
        cycle++;
        
        if (tort == hare) break;
    }
    
    cout << cycle;
    
    return 0;
}

    This isn’t a perfect solution - I know I have personal coding idiosyncrasies, and it doesn’t take into account edge cases such as N == 0 or P == 0 - but it does streamline Floyd’s solution with the knowledge of the limit N and does so in under 40 lines of code.

    Hopefully this inspires others to go back to the research when they get the “Time limit exceeded” on their test case(s).

  • Tixanthalee
     + 0 comments

    Working one. No more sprawling sets.

    #include <iostream>
#include <vector>
using namespace std;

bool seenIT(unsigned long long sCurrent, vector<unsigned long long>& seen) {
    size_t blk = sCurrent >> 6;
    unsigned long long slot = 1ULL << (sCurrent & 63);
    if (seen[blk] & slot) return true;
    seen[blk] |= slot;
    return false;
}

int main() {
    unsigned long long n, s, p, q;
    cin >> n >> s >> p >> q;

    const unsigned long long RANGE = 1U << 31;            //this many different #s
    size_t blocks = (RANGE + 63) / 64;
    vector<unsigned long long> seen(blocks, 0);         //All start as 0, unseen
    seenIT(s, seen);
    
    bool earlyOut = false;
    for (int i = 1; i < n; i++) {
        s = (s * p + q) % RANGE;
        if (seenIT(s, seen)) {
            earlyOut = true;
            cout << i;
            break;
        }
    }
    if (!earlyOut)
        cout << n;

    return 0;
}

  • Tixanthalee
     + 0 comments

    The simplest solution, but sadly it didn't like my time

    #include <iostream>
#include <set>                          // ******
using namespace std;

int main() {
    int n, s, p, q;
    cin >> n >> s >> p >> q;
    
    const unsigned int range = 1U << 31;
    
    int num = s;
    set<int> a;
    a.insert(num);
    for(int i = 1; i < n; i++){
        num = (num*p+q) % range;
        a.insert(num);
    }
    cout << a.size();
    
    return 0;
}

  • vishnut0308
     + 0 comments
    #include <iostream>
#include <algorithm> 
//nicely trolled hackerrank..well done..u alomost destroyed my PC
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    unsigned long long n, s, p, q;
    std::cin >> n >> s >> p >> q;
    if (n == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }
    if (p == 0) {
        unsigned long long a_1 = q;
        if (s == a_1) std::cout << 1 << std::endl;
        else std::cout << std::min(n, 2ULL) << std::endl;
        return 0;
    }
    if (p == 1 && q == 0) {
        std::cout << 1 << std::endl;
        return 0;
    }
    const unsigned long long MASK = (1ULL << 31) - 1;
    unsigned long long tortoise = s;
    unsigned long long hare = s;
    bool cycle_found = false;
    for (unsigned long long i = 0; i < n; ++i) {
        tortoise = (tortoise * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        if (tortoise == hare) {
            cycle_found = true;
            break;
        }
    }
    if (!cycle_found) {
        std::cout << n << std::endl;
        return 0;
    }
    unsigned long long mu = 0;
    tortoise = s;
    while (tortoise != hare) {
        tortoise = (tortoise * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        mu++;
    }
    unsigned long long lambda = 1;
    tortoise = (tortoise * p + q) & MASK;
    while (tortoise != hare) {
        tortoise = (tortoise * p + q) & MASK;
        lambda++;
    }
    std::cout << std::min(n, mu + lambda) << std::endl;

    return 0;
}

  • godisblaaack
     + 0 comments
    #include <iostream>
using namespace std;

const unsigned long long MOD = 1ULL << 31;
const int BITSET_SIZE = MOD / 64; // Number of 64-bit blocks (approx 33.5 million)

unsigned long long mask[BITSET_SIZE] = {0};

bool insert(unsigned x) {
    unsigned idx = x >> 6;    // Divide by 64 to get block index
    unsigned pos = x & 63;    // Modulo 64 to get bit position
    if ((mask[idx] & (1ULL << pos)) == 0) {
        mask[idx] |= (1ULL << pos);
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long N, S, P, Q;
    cin >> N >> S >> P >> Q;

    unsigned long long a = S % MOD;
    unsigned long long distinct = 0;

    // Insert first element
    if (insert(a)) distinct++;

    for (unsigned long long i = 1; i < N; i++) {
        a = (a * P + Q) % MOD;
        if(insert(a))
            distinct++;
    }

    cout << distinct << "\n";
    return 0;
}