Problem 1

If numbers are to big to fit into standard data types, then we can use strings to store the number. In this case, addition of two number would require doing digit by digit addition along with required carry over getting transferred to the next higher order cell. Lets suppose that the longer of two of the input numbers is of length L. Then the size of the result would be at maximum L+1. Now, for doing addition, you need to place two separate indices at the end of the two numbers annd do an addition of the two digits there. Beware that the two digits are stored in character format, so subtract 10 from each of them before adding them. If this addition results in a number greater than 10, then write down the unit digit of the result in right most cell of the result string and note down the carry forward. If the result of the addition is less than 10 then then no need to worry about the carry forward. Now repeat this process by having moved all the three indices one place to the left, and keep repeating till the longer of the two numbers is traversed. If one of the input number runs out of digits then assume it to be supplying 0. Finally, output the result string on the screen.

Problem 2

A number x is said to be a square root of N if xx=N.Thus is it quite obvious that the square root a positive integer > 1 lies in between [1 N]. Suppose P is a number such that PP > N then the result must be in the interval [1 P-1] oterwise if PP < N then the result lies in [P+1 N]. We use this idea to find the square root of a positive integer. Suppose we know that the square root lies in between (start,end).If mid = (start+end)/2.0, depending upon the value of midmid-N we chose either (mid+1,end) or (start,mid-1) as our next search interval or conclude that mid is the square root of N.While coding do take care of the fact of precision since mid*mid may not be exactly equal N.

Time complexity

If you analyze the number of operations it takes this function to run it is easy to see that it will take logN (logN to base 2) operations. At every step of the search we chose either (start,mid-1) or (mid+1,end) which means the interval size gets reduced by half. Initially the range is N, in the next step it will become N/2, then N/4, and so after x steps the search range will be N/(2^x) which will be 1 when x is logN. So, the number of iterations is log(N).