Problem Solving:: Be Like Hasib from Toph

Tag of this problem is binary search. Binary search problems seems very interesting to me.  Without thinking much about the problem I submitted a simple binary search algorithm. But got wrong answer 5 or 6 times. But after carefully reading the statement I understood I have to make change to my binary search algorithm.
Modified Binary Search::
int count=0;
    ll mid=-1;
    while(l<h)
    {
        mid=(l+h)/2;
        count++;
        //cout<<l<<" "<<h<<" "<<mid<<endl;
        if(x==mid)
        {
            h=mid;
            continue;
        }
        if(x<mid)
            h=mid;
        else l=mid+1;
    }
Then got accepted. it was a nice practice problem.  A good way to start a day.

Comments

Post a Comment

Popular posts from this blog

Java notes Date:26/11/2019

#Like C++, when a function is static, run time polymorphism doesn't happen in Java. #Final methods cannot be overridden. #In Java, functions are virtual by default.  #Private methods are final and can not be overridden.   #It is compiler error to give more restrictive access to a derived class function which overrides a base class function. #A java array is always an object. #Arrays in Java are always allocated on heap.  
Read more

Problem Solving :: Largest Prime from Toph

In this problem, task is to find out the largest prime number in a given range. Statement says Q (1 ≤ Q ≤ 10 ^5 ), the number of queries that will be given. The next Q lines will contain two integers l i (1 ≤ l i ) and r i (r i ≤ 10000). So for solving this, I used a sieve algorithm for storing all the prime numbers is an array from 1 to 10000. Then I apply binary search for each query.
Read more