find count of nos less than a given no which have power of 2 greater than a reqd value in their prime factorization…
Eg if given no is 90 and we want to find count of all nos be 1 and 90 having power of 2 greater than 1 in their prime factorization…how would I do that in logn complexity…
Plz provide the code as well…
Prime factorization problem
@S19LPPP0202 you just have to find the smallest number having power greater than lets say k.
lets take your example n=90 and you want power of 2 greater than 1 that is 4 so you need to find just no of multiples of 4 (as they will always containg atleast two twos) in 1 to 90.
it can be given by n/4 ( in o(1) no logn required) so ans 90/4=22
note that if you want k to be big like have to find greater then 10th power of 2 so use fast power method to calculate pow(2,something) and then it will take logn time
dont forget to hit like and mark resolved if cleared 
plz reply to this doubt of mine as well.this is unresolved…
click on this link and plz reply to this doubt of mine as well at the earliest…
it would be really helpful
@S19LPPP0202 i used the brute force approah as the constraints are very less my code takes o(n*n) time. what i did was as in the question ans string can only be formed like this 00111 , 11000 ,00111,00000,11111, 011111 so i made all the possible strings out of it like if
string = 101
i made 000 001 011 111 100 110 and compared each of them with original string and stored the answer and final ans mimimum of all here is the code -
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.