@manmeet so, please choose your nickname at the forum :)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@goo
@ juver++ : fight is my tc handle. here u can call me manmeet :) :)
On Fri, Jan 21, 2011 at 9:35 PM, juver++ wrote:
> @fight good solution.
> 3^n contains only one 1 in the 3-base representation.
> So write number M in base-3, and check if it contains only one digit(1).
> There is no need to fi
@fight good solution.
3^n contains only one 1 in the 3-base representation.
So write number M in base-3, and check if it contains only one digit(1).
There is no need to find & with M-1.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post
write n, n-1 to base 3
check if thr & gives 0, if it gives no. is of form 3^n
On Fri, Jan 21, 2011 at 8:04 PM, snehal jain wrote:
> @manmeet
> how?
>
>
> On Fri, Jan 21, 2011 at 7:36 PM, Manmeet Singh wrote:
>
>> @juver++ : the above is a user defined function. but its possible to the
>> problem
@manmeet
how?
On Fri, Jan 21, 2011 at 7:36 PM, Manmeet Singh wrote:
> @juver++ : the above is a user defined function. but its possible to the
> problem using bit wise operators.
>
>
> On Fri, Jan 21, 2011 at 7:29 PM, juver++ wrote:
>
>> @above it's a user-defined function using fast exponentiat
@juver++ : the above is a user defined function. but its possible to the
problem using bit wise operators.
On Fri, Jan 21, 2011 at 7:29 PM, juver++ wrote:
> @above it's a user-defined function using fast exponentiation
>
> --
> You received this message because you are subscribed to the Google G
@above it's a user-defined function using fast exponentiation
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr..
@snehal : YUP
On Fri, Jan 21, 2011 at 5:57 PM, abhijith reddy wrote:
> @snehal .. misread it .. my apologies.
>
>
> On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy
> wrote:
>
>> O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
>> M=3^x
>> We binary search on x and then compu
@snehal .. misread it .. my apologies.
On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy wrote:
> O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
> M=3^x
> We binary search on x and then compute 3^x in log(x) time using
> exponentiation. Hence the complexity.
>
>
>
> On Fri, Ja
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
M=3^x
We binary search on x and then compute 3^x in log(x) time using
exponentiation. Hence the complexity.
On Fri, Jan 21, 2011 at 5:50 PM, snehal jain wrote:
> @juvir++
> it was mentioned in question not to use log or power.
@juvir++
it was mentioned in question not to use log or power. isnt there any
approach using bitwise operators
On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh wrote:
> this will be O(log(n) * log(n)) solution
>
>
> On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy
> wrote:
>
>> Below is code for mo
this will be O(log(n) * log(n)) solution
On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy wrote:
> Below is code for modular exponentation in general
>
> // (a^b)%c
> int modexp(int a,int b,int c)
> {
>int ans=1;
>while(b)
>{
> if(b&1) ans=(ans*a)%c;
> a=(a*a)%c;
> b>>=1
Below is code for modular exponentation in general
// (a^b)%c
int modexp(int a,int b,int c)
{
int ans=1;
while(b)
{
if(b&1) ans=(ans*a)%c;
a=(a*a)%c;
b>>=1;
}
return ans;
}
On Fri, Jan 21, 2011 at 3:27 PM, juver++ wrote:
> int l = 0, r = ...;
> while (l < r) {
>
int l = 0, r = ...;
while (l < r) {
int m = (l + r) / 2;
int p = power(3, m);
if (p > M) r = m - 1;
else if (p < M) l = m + 1;
else print 3^m = M;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email t
@ above
m nt getting binary search and fast exponentiation .. please elaborate.
On Fri, Jan 21, 2011 at 2:07 PM, juver++ wrote:
> The most well done solution is to store possible powers of 3 in a table
> (this table will be small), and then try to find number M.
>
> --
> You received this messa
The most well done solution is to store possible powers of 3 in a table
(this table will be small), and then try to find number M.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.co
binary search on the answer and then fast exponentiation.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@go
Number exponentiation
On Fri, Jan 21, 2011 at 1:05 PM, snehal jain wrote:
> Given M, find if M = 3^x for some positive integer x efficiently. DO
> NOT think of log, pow etc
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to t
Given M, find if M = 3^x for some positive integer x efficiently. DO
NOT think of log, pow etc
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, se
19 matches
Mail list logo
