Alice and Bob's Silly Game
Alice and Bob's Silly Game
+ 0 comments JavaScript Solution
let ans = 0 if (n === 1) return "Bob" else ans++ // because n>0 function isPrime(i) { // optimal the loop condition let limit = Math.round(Math.sqrt(i)) for (let mod = 2; mod <= limit; mod++) { if (i % mod === 0) { return false; } } return true } // eleminate the even number except 2 to optimal the loop for (let i = 3; i <= n; i += 2) { if (isPrime(i)) ans++ } return ans % 2 === 0 ? "Bob" : "Alice"
+ 0 comments Here is Alice and Bob's Silly game problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-alice-and-bobs-silly-game-problem-solution.html
+ 0 comments Linear Sieve+Prefix Sums
void sive(){ memset(lp,0,sizeof lp); for (int i=2; i<=N; ++i) { if (lp[i] == 0) { lp[i] = i; pr.push_back (i); } for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j){ lp[i * pr[j]] = pr[j]; } } a[0]=a[1]=0; for(int i=2;i<mxn;i++){ if(lp[i]==i){ a[i]=a[i-1]+1; continue; } a[i]=a[i-1]; } } void test_case(){ int n,cnt=0; read(n); if(n<2){ cout<<"Bob"<<endl; return; } cnt=a[n]; cout<<(cnt&1?"Alice":"Bob")<<endl; } int main(){ int tt; sync(); read(tt); sive(); while(tt--){ test_case(); } }
+ 0 comments Here is my simple algorithm to solve the problem. I won't tell the code as so many people here have already done without explaining anything. I created a function which takes int n input and returns total count of prime numbers form 1 to n including. Now, if n is even, answer is "Bob" else it is "Alice". Now this method passes three test cases but time limit exceeds in two other test case. What I observed is that, on single test case, multiple inputs are being taken, so calculating everytime the count of prime numbers is redundant. So, I created some global arrays to store the count and when it repeats, I supply it from there. Reply if you need more explanation or code.
+ 0 comments In C#: public static string sillyGame(int num) { if (num < 3) return num % 2 == 0 ? "Alice" : "Bob"; bool[] primes = new bool[num + 1]; primes[0] = primes[1] = true; for (int idx = 4; idx < num + 1; idx += 2) primes[idx] = true; // exclude int cnt = 1; // {2} for (int i = 3; i <= num; i += 2) { if (!primes[i]) { cnt++; for (int idx = 2 * i; idx < num + 1; idx += i) primes[idx] = true; } } return primes.Where(p => !p).Count() % 2 == 1 ? "Alice" : "Bob"; }
Looks similar to ojava
Sort 53 Discussions, By:
Please Login in order to post a comment