CareerCup

#include <iostream>
using namespace std;
int main()
{
int x = 3;
int y =4;

int i = 1;
while (i < y)
{
x*=x;
i*=2;
}
cout<<"result="<<x;
return 0;
}

- kk.nitrkl January 25, 2012 | Flag Reply

can we still write more efficient algo for the case when y=2^n.
eg: y=2^13
where n=13 ~= 1101. And applying some bit arithmatic here . Interviewer give me only this much of hint . How to reach to a solution from here??

- priyankajaggi4 January 25, 2012 | Flag Reply

we can use Divide and Conquer to do so

X^y= X^(y/2) * X^(y/2) : if y is even
=X^(y/2) * X^(y/2) *X : if y is odd

Further small powers can be percalculated and the answer to recursion is the answer !

- scofield January 25, 2012 | Flag Reply

If y = 2^n,

x^y = x << n.

- vijay January 25, 2012 | Flag Reply

#include<iostream>
#include<string>
using namespace std;

int z;
int pow(int x, int y){

if (y==0)
return 1;

if(y%2==1)
{
z=pow(x,(int)(y/2));
x=z*z*x;
}
else
{
z=pow(x,(int)(y/2));
x=z*z;
}
return x;
}

int main()
{
int x,y;
while(cin>>x>>y)

cout<<pow(x,y)<<endl;

return 0;

}

- Anonymous January 27, 2012 | Flag Reply

int pow(int a, int b)
        {
            int result = 1;
          
            while (b!= 0)
            {               
                if ((b& 1) > 0)
                    result *= a;
                b>>= 1;
                a *= a;
            }          

            return result;
     }

- Ran January 27, 2012 | Flag Reply

{{{use divide and conquer method .... i.e if y=2n (even) then z=y^n; answer=n*n; else z=y^n; answer=n*n*y; so, T(n)=T(n/2)+constant time; - damodarnitt January 27, 2012 | Flag Reply

{{{use divide and conquer method .... i.e if y=2n (even) then z=y^n; answer=n*n; else z=y^n; answer=n*n*y; so, T(n)=T(n/2)+constant time; - damodarnitt January 27, 2012 | Flag Reply

/*Write an efficient power function.
int power (int x, int y) for calculating x^y,
especially for the case that y is of the form 2^n.*/
function pow( x, y){
/* Cases:       x^0 = 1
                x^1 = x
                x^y = z
                x^(2^n) = z
*/
        if ( y < 2 ) {
                var ret;
                (y == 0) ? ret = 1 : ret = x;
                return ret;
        }
        var isOdd = (y & 1);
        if (!isOdd) {
                return pow(x * x, y/2);
        } else {
                return x * pow(x * x, (y-1)/2);
        }

}

- srt January 27, 2012 | Flag Reply

If y=2^n you just need to right shift by n

#include<stdio.h>

int main()
{
        int n,x;
        scanf("%d",&x);

        scanf("%d",&n);

        printf("%d",x<<n);
}

- Kesha May 21, 2013 | Flag Reply

int pow(int x, int y){
        
        int result=x,rem;
        if(y==0)
            return 1;
        else if(y==1)
            return x;
        else{
            int i = 1;
            while(i*2<=y){
                result = result*result;
                i=i*2;
            }
            rem = y%i;
            if(rem!=0){
                result = result *pow(x,rem);
            }
        }
    return result;
    }

- Shreshtha December 26, 2016 | Flag Reply