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

- 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)
- 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.
- GCD – Euclidean algorithm – Solutionint gcd(int a, int b)

{

if (a == 0)

return b;

return gcd(b%a, a);

}
- 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!

### Like this:

Like Loading...

*Related*