In Which Test Case This Code Will Fail?

general
, , , ,
1

Problem : Monsters Practice Coding Problem - CodeChef
Code :
include <bits/stdc++.h>
define ll long long
define endl “\n”
define MAX_LIMIT 1000000
define FAST cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0)
using namespace std;

vector generatePrimes(int num) {
vector primes;
bool isPrime[num + 1];
memset(isPrime, true, sizeof(isPrime));
for (int i = 2; i * i <= num; i++) {
if (isPrime[i]) {
for (int j = i * 2; j <= num; j += i)
isPrime[j] = false;
}
}
for (int i = 2; i <= num; i++)
if (isPrime[i])
primes.push_back(i);
return primes;
}

bool isPrime(int num) {
if (num <= 1)
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)
return false;
}
return true;
}

bool isSumOfPowersOf2(int n) {
return ((n & (n + 1)) == 0);
}

int main() {
FAST;

vector<int> primes = generatePrimes(MAX_LIMIT);
int n = primes.size();

int tc;
cin >> tc;

while (tc--) {
    int h;
    cin >> h;

    int ans = INT_MAX;
    if (h >= 2 && isSumOfPowersOf2(h)) {
        ans = __builtin_popcount(h);
    }

    if (h >= 2) {
        int ind = upper_bound(primes.begin(), primes.end(), h) - primes.begin();

        if (ind == n)
            ind--;

        for (int i = ind - 1; i >= 0; i--) {
            if (primes[i] <= h) {
                int num = h - primes[i];
                if ((num & (num + 1)) == 0) {
                    int jumps = __builtin_popcount(num) + 1;
                    ans = min(jumps, ans);
                }
            }
        }
    } else {
        ans = -1; // Unable to kill the monster
    }

    ans!=INT_MAX?cout << ans << endl:cout<<-1<<endl;
}

return 0;

}

2

Seems like you are overcomplicating things

3

@meet2409
not getting your logic at all.
plzz refer the following code for better understanding of the implementation

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
bool isprime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n<=1)return false;
        if(n%i==0){
            return false;
        }
    }
    return true;
}

int main() {
	int t;
	cin>>t;
	
	
	for(int i=0;i<t;i++){
	    int h;
	    cin>>h;
	   int count=0;
	   int ap=1;
	   
	 
	   while(h>0){
	         if(isprime(h)){
	           h=0;
	           count++;
	           break;
	       }
	       else{
	       
	       h=h-ap;
	       ap=2*ap;
	       count++;
	       }
	   }
	   if(h!=0){
	       cout<<-1<<endl;
	   }
	   else{
	       cout<<count<<endl;
	   }
	 
	}
	return 0;
}
4

Thank You For Your Quick Response.

My Approach in Code

  1. Generate all Prime Numbers (as Here Health 1≤H≤10^6)
  2. Now To Reduce Health To Zero We Have Two Options Either Reduced By Power of 2 (First By 2^0,2^1,…) or Reduce Prime Number From Health H.
  3. So I Decided That Let’s First Check Whether Number’s all Bit are Set Or Not.If Yes Then We Can Reduce That Health By Substracting Power of 2.
  4. Now Question Aries that How Much Operaions Needed That Will Be Equivalent to Number of Set Bit In Number.
  5. Later I Try All The Prime Number Which is Less than Or Equal to Given Health and Whatever Number Comes After Substracting Prime Number From H, I Checked Whether That Number is Also SUm of Power of 2.

I Checked For all Prime Numbers Less Than Health H.Minimum of Them is Stored in ans.

5

Thank You Bhai For Your Caring Reply and Sorry For The Delay in Response.

My Logic

  1. Assume There is No Prime Moves Then Number Will Be Sum of Power of 2 Then All Bits are Set in it.Then Answer Will Be Number of Set Bits.

  2. If There is a Prime Move Then (Number - Prime Number) Will Have all the Bit Set Then Answer is Set Bits + 1(For Prime Move).

Here I Tried All The Bits Less Than Health To Get Minimum Moves.

May Be My Logic is Wrong But i Not Able to Find On Which TestCases I Wrong.

6

@meet2409
yes your logic is right
but i guess u have made your code over complex.
just stick to your logic and try to implement it again.

7

Yah thats why you should think how complex and lengthy it would to genrate all the prime numbers if you were given a large number …Your logic is right but try making it optimal and efficient.
Also working into binary number is not always faster and better