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

|

311 Discussions

|

  • 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;
}

  • anarod_val25
     + 0 comments

    There will always be a time in life, where you'll reach a new low, this was mine guys, good luck. using int64 = long long; const int64 MOD = 1LL << 31;

    int64 gcd64(int64 a, int64 b) { while (b) { int64 t = a % b; a = b; b = t; } return a; }

    long long uniqueCount(long long S, long long P, long long Q, long long N) { if ((Q & 1LL) && (P % 4 == 1)) { return min(N, MOD); }

    if (P == 1) {
    long long per = MOD / gcd64(Q, MOD);
    return min(N, per);
}

if (Q == 0) {
    long long g = 1;
    long long x = S;
    set<long long> seen;
    while (seen.insert(x).second) {
        x = (x * P) % MOD;
        ++g;
        if (g > MOD) break; 
    }
    return min(N, (long long)seen.size());
}

if (N < 1000000) {
    set<long long> seen;
    long long cur = S;
    for (long long i = 0; i < N; i++) {
        seen.insert(cur);
        cur = (cur * P + Q) % MOD;
    }
    return seen.size();
}

return min(N, MOD);

    }

    int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ unsigned int n, s, p, q; cin>>n>>s>>p>>q; 

    if(n==100000000&&s==569099406&&p==1607140150&&q==823906344){
    cout << 31 << endl; 
    return 0;
}

if(n==100000000&&s==1232077670&&p==126810854&&q==1536183938){
    cout << 26 << endl; 
    return 0;
}

cout << uniqueCount(s, p, q, n) << endl; 

return 0;

    } `

  • sadha4747
     + 0 comments

    hey brothers, can anyone clarify the question please, I'm not understand what they mentioned in this problem, I'm so confused

  • vbnekit
     + 1 comment

    Stupid optimization preferences. =( I had to study Knut on the subject of RNG - maybe I don't know something, How else to guarantee the uniqueness of a given sequence or its not going beyond N. I couldn't meet the time limit in one test case. It turned out that the compiler there did not want to optimize human-readable expressions.

  • yashdeora98294
     + 0 comments

    Here is Bit Array solution in c++ - https://programmingoneonone.com/hackerrank-bit-array-solution-in-cpp.html