Fundamental Problem

Problem that can’t be put into any major category –

  1.  Square root of an integer – One approach is to do a normal looping checking for every no. that there square is less then the given number.Time complexity of the above solution is O(√ x) where  x= no for which sq. root is to be calculated
    Another approach is using binary search. Just start binary search from no 1 to the given no. If the mid value sq. is greater then then given no. then change the range for the binary search.
    Time Complexity: O(Log x)
    As the value of x increases O(Log x) performs better then O(√ x)
  2. Cube root of a no. – Use the same binary search approach as above but now we will increase the accuracy by checking the limit of error.
  3. GCD – Euclidean algorithmSolutionint gcd(int a, int b)
    {
    if (a == 0)
    return b;
    return gcd(b%a, a);
    }
  4. LCM –  LCM of 2 numbers is the product of 2 numbers divided by the gcd of the numbers. The following is the code snippet for LCM of 2 numbers:

    int lcm  (int a, int b)   { return (a * (b / gcd(a, b))); } // divide before multiply!

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s