Amazon Interview Question
InternsCountry: India
Newton-Raphson method
def sqr3(n):
... k = 1.0
... while((k*k - n) > 0.0000000001 or (n - k * k) > 0.0000000001):
... k = (k + n / k) / 2
... return k
#include <stdio.h>
int main()
{
int n;
printf("Enter your number:");
scanf("%d", &n);
int s;
for(s = 1; s*s <= n; s++);
s--;
double x;
for(double d = 0.001; d < 1.0; d+= 0.001)
{
x = (double)s + d;
if((x*x > (double)n))
{
x -= 0.001;
break;
}
}
printf("square root is %.3lf\n", x);
return 0;
}
Below is a code that computes the square root of an integer and only returns the integer part. However this can be generalized to return floating point also ( by defining some error margin) . I just wanted to discuss about the idea. The idea I used is binary search. The squares of the natural numbers are already sorted , for example, 1,4,9,16.. and so on. So initially low = 1, and high = n. And in every iteration calculate mid = (low+high)/2 and check if (mid*mid) is less than , greater than or equal to the given element and update the mid value accordingly.
#include<stdio.h>
int square_root_binary_search(int elt)
{
int low,high,mid;
low=1;
high=elt;
while(low<=high)
{
mid = (low+high)>>1;
if(mid*mid == elt) return mid;
if(mid*mid > elt)
high = mid -1 ;
else
low = mid + 1;
}
return high;
}
int main()
{
int elt;
printf("Enter the number");
scanf("%d",&elt);
printf("The square root is %d\n",square_root_binary_search(elt));
return 0;
}
Above code has a compilation error in the statement mid = (low+high)>>;1;
an extra semicolon is there. The rest is fine. The complexity of this code in O(logn). However if you want to return the exact square root then you need to define some error margin, say "e". In that case the complexity will be O(log(n/e)).
float sqrrt( int a) // for a>3
{
int b;
float temp,temp2=0;
cout<<"Enter the number of decimal precision :";
cin>>b;
for(int i=1; i<=a/2;i++)
{
if(i*i>a)
{
temp=i-1;
break;
}
temp2=temp;
for(i=1;i<=b;i++)
{
for(float j=0;(temp2*temp2)<a;j++)
{
temp2=temp1;
temp2=temp2+ (j/(10^i));
}
temp2=temp;
temp2=temp2+ ((j-1)/(10^i));
temp=temp2;
}
return temp;
}
this can be done in an other way too
when given a number, start subtracting all the odd numbers from it sequentially
if we get a 0 in the end, the number is a perfect square, and the number of times the subtraction is performed, is the square root of the number
even though this approach is not good for very big integers, it will work fine for small ones
e.g 25
25-1=24
24-3=21
21-5=16
16-7=9
9-9=0
this means that 25 is a perfect square and 5 is the square root
#include<conio.h>
#include<stdio.h>
void main()
{
float a,b,n=47;
clrscr();
a=n;
do
{
b=a;
a=(a+n/a)/2;
}while(a!=b);
printf("%f",a);
getch();
}
Note: Java Code & running for all cases:
Case 1: Negative number
Case 2: 0<=n<=1
Case 3: n>1
public static double sqrtMethod3(double a)
{
//firstly check if a is non-negative value
if(a<0)
return -1;
//also check if a==0 or a==1 because in these two cases sqrt(a) = a
if(a==0 || a==1) return a;
//now start the core part of the code
double precision = 0.0000000000001;//define the precision, so we stop when precision is achieved
double start = 0;
double end = a;
//we define these two start/end values because usually 0<sqrt(a)<a
//however, if a<1; then 0<a<sqrt(a)
if(a<1)
end = 1;
//define a loop to continue if the precision is not yet achieved
while(end-start>precision)
{
// System.out.println("end-start = "+(end-start));
// System.out.println("precision = "+precision);
double mid = (start+end)/2;
double midSqr = mid*mid;
if(midSqr==a)
return mid;//we find the exact sqrt value!
else if(midSqr<a)
start = mid;//we shift our focus to bigger half
else
end = mid;//shift focus to smaller half
}
//if we did not find exact sqrt value, we return the approxiated value with the defined precision
return (start+end)/2;
}
here is update to my previouus commenrt dated 14 july
int main()
{
int t;
scanf("%d",&t);
int input[10001];
char temp_s[25];
for(int k=0;k<t;k++) {
int n,query;
LL temp_res=0,x_ll;
double x_d;
scanf("%d%d",&n,&query);
for(int i=0; i<n; i++) {
scanf("%d",&input[i]);
if(input[i]<0) input[i]+=MOD;
temp_res = (temp_res+input[i])%MOD;
}
for(int i=0; i<query; i++) {
scanf("%lld",&x_ll);
sprintf(temp_s,"%lld",x_ll);
sscanf(temp_s,"%lf",&x_d);
LL ans=temp_res,temp_ans;
int index=1;
while(1) {
if(x_ll == 1) break;
if(index == 1) temp_ans=x_ll;
else {
temp_ans=pow(x_d,1.0/index)+1e-7;
if(pow(temp_ans,index)>x_d) temp_ans--;
}
if(temp_ans == 1) break ;
temp_ans--;
temp_ans=temp_ans%MOD;
ans = (ans+(input[index-1]*temp_ans)%MOD)%MOD;
index++;
}
cout<<ans<<" ";
}
cout<<endl;
}
return 0;
}
Update to code helpful to solve maxpr problem in codechef
for(int i=1; i<n; i++) {
for(int d=0; d<=a[i]; d++) {
dp1[a[i]][d] = (dp1[a[i]][d] + dp1[a[i]-d][d])%M;
if(!d) dp1[a[i]][d] = (dp1[a[i]][d]+1)%M;
if(d) dp1[a[i]][d] = (dp1[a[i]][d]+freq[a[i]-d])%M;
}
for(int d=1; d+a[i]<=100; d++) {
dp2[a[i]][d] = (dp2[a[i]][d] + dp2[a[i]+d][d])%M;
dp2[a[i]][d] = (dp2[a[i]][d]+freq[a[i]+d])%M;
}
freq[a[i]]++;
total = (2*total)%M;
/*for(int k=0; k<=4; k++) {
for(int j=0; j<=3; j++)
cout<<dp1[k][j]<<" ";
cout<<endl;
}
}
int ans=total-1;
int ans1=0,ans2=0;
for(int i=0; i<=100; i++)
for(int d=0; d<=100; d++) {
ans1 = (ans1+dp1[i][d])%M;
ans2 = (ans2+dp2[i][d])%M;
}
ans = ans-ans1; if(ans<0) ans += M;
ans = ans-ans2; if(ans<0) ans += M;
#include<iostream>
#include<stdio.h>
using namespace::std;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n;
scanf("%d",&n);
int temp=0,max=0;
for(int i=0; i<n; i++) {
int a;
scanf("%d",&a);
if(a) temp++;
else {
if(max<temp) max=temp;
temp=0;
}
}
if(max<temp)
max=temp;
printf("%d",max);
return 0;
}
#include<stdio.h>
/*Returns the square root of n. Note that the function */
float squareRoot(float n)
{
/*We are using n itself as initial approximation
This can definitely be improved */
float x = n;
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
printf("%f == %f\n",x,y);
}
return x;
}
void main(){
float ab;
printf("enter the number\n");
scanf("%f",&ab);
printf("%lf this is the float vallues\n",squareRoot(ab));
printf("original values==%lf\n",squareRoot(ab)*squareRoot(ab));
}
Can use Babylonian Method..
#include<iostream>
using namespace std;
float squareroot(float n)
{
float x = n;
float y = 1;//can be other constant
float e = 0.000001;
while(x-y>e){
x =(x+y)/2;
y = n/x;
}
return x;
}
int main()
{
int n;
cout<<"Enter the number"<<endl;
cin>>n;
cout<<squareroot(n)<<endl;
return 0;
}
I know the question was for C, but for simplicity, I coded up in ruby. Should be similar in C
Based on newton raphson method.
- swap1712 August 14, 2013How fast it produces an answer, depends on your initial guess. One can use a lookup table for that or simply default the init_guess to 1. If one does not want to pass arguments except for x, one can write a wrapper around this code.
For more on NR method, check out this video:
http://mathforcollege.com/nm/videos/youtube/03nle/newtonraphson/newtonraphson_03nle_squarerootnewtonraphson.html