u people absolutely correct that log operation take much time , i just
given an approach
On Sat, Dec 10, 2011 at 7:25 AM, Dave dave_and_da...@juno.com wrote:
@Gaurav: Even though this is O(log n), it is bound to be slow, since
it would use division and modulus are among the slowest operations
@Gaurav: Even though this is O(log n), it is bound to be slow, since
it would use division and modulus are among the slowest operations on
modern computers, some of which don't even have an integer division
instruction. Here is a revision to my earlier code, for 32-bit
integers. It should be
what about this log(base 3 n) is of integral type then n is a power of 3
On Mon, Dec 5, 2011 at 11:36 PM, Dave dave_and_da...@juno.com wrote:
@Carl: You can generate the constants the first time the procedure is
called. There is no need to do them every time. So the first call
would be
Originaly problem rules out the use of log.Moreover log (or any floating
point operations) take lot of hardware time as they are emulated on the
floating point environment on most machines.Thirdly precision problem for
higher values of n may cause your solution to give wron g answers,,,
On Wed,
@SAMMM have a look
* *solution is to keep dividing the number by 3, i.e, do n = n/3
iteratively. In any iteration, if n%3 becomes non-zero and n is not 1 then
n is not a power of 3, otherwise n is a power of 3
check it out ? http://codepad.org/863ptoBE
Thanks
Shashank
Computer Science
BIT
@WgpShashank: Yours is an O(log n) solution. Mine is O(1).
Dave
On Dec 5, 6:21 am, WgpShashank shashank7andr...@gmail.com wrote:
@SAMMM have a look
* *solution is to keep dividing the number by 3, i.e, do n = n/3
iteratively. In any iteration, if n%3 becomes non-zero and n is not 1 then
n
@Dave Yours only works for a certain subset of all possible powers or 3
doesn't it? So WgpShashank's would be more general?
On 5 December 2011 14:30, Dave dave_and_da...@juno.com wrote:
@WgpShashank: Yours is an O(log n) solution. Mine is O(1).
Dave
On Dec 5, 6:21 am, WgpShashank
@Carl: Yes, as coded, my algorithm is for 32-bit integers. But the
original poster asked for a solution using bit manipulation, and
modulus and division are arithmetic operations, not bit operations.
Dave
On Dec 5, 8:56 am, Carl Barton odysseus.ulys...@gmail.com wrote:
@Dave Yours only works
Ah I see, in which case could you not generalise your solution for all
integers?
By taking into account the size of words on the computer for example?
On 5 December 2011 15:09, Dave dave_and_da...@juno.com wrote:
@Carl: Yes, as coded, my algorithm is for 32-bit integers. But the
original
@Carl: Of course. For any given word size, extend the tables of powers
of 2 and of 3 and change the for loop limit.
Dave
On Dec 5, 9:36 am, Carl Barton odysseus.ulys...@gmail.com wrote:
Ah I see, in which case could you not generalise your solution for all
integers?
By taking into account the
Sorry, I was being a bit vague. I meant what would the time complexity be
then?
As I understand your Constant time is Dependant on the constant pre
computation you do, which is no longer the case when you generalise
On 5 December 2011 16:14, Dave dave_and_da...@juno.com wrote:
@Carl: Of course.
@Carl: You can generate the constants the first time the procedure is
called. There is no need to do them every time. So the first call
would be O(wordsize) but subsequent calls are O(1).
Dave
On Dec 5, 10:28 am, Carl Barton odysseus.ulys...@gmail.com wrote:
Sorry, I was being a bit vague. I
@SAMM: Something like this might work:
bool PowerOfThree(unsigned int n)
{
int powsof2[5] = {16,8,4,2,1};
int powsof3[32] =
{1,3,0,9,27,0,81,243,0,729,0,2187,6561,0,19683,59049,0,177147,0,531441,1594323,0,
4782969,14348907,0,43046721,129140163,0,387420489,0,1162261467,3486784401};
@nitin it must be 2^n i think
On Aug 17, 3:48 am, Bharat Kul Ratan bharat.kra...@gmail.com wrote:
It might be
useful:http://www.artofproblemsolving.com/Wiki/index.php/Partition_%28combin...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
my bad 2^(n-1)...
On Aug 17, 2:17 pm, Vijay Kansal vijaykans...@gmail.com wrote:
@nitin it must be 2^n i think
On Aug 17, 3:48 am, Bharat Kul Ratan bharat.kra...@gmail.com wrote:
It might be
useful:http://www.artofproblemsolving.com/Wiki/index.php/Partition_%28combin...
--
You
+1 to nitin
On Wed, Aug 17, 2011 at 2:48 PM, Vijay Kansal vijaykans...@gmail.comwrote:
my bad 2^(n-1)...
On Aug 17, 2:17 pm, Vijay Kansal vijaykans...@gmail.com wrote:
@nitin it must be 2^n i think
On Aug 17, 3:48 am, Bharat Kul Ratan bharat.kra...@gmail.com wrote:
It
I think it should be 2^n -1
Explanation
We can visualize it as n balls are placed and we have to place some dividers
(max=n) in betweek to divide them into groups.
If we choose no divider its nC0 , but we dont have to include it
With 1 divider its nC1
and so on..
So the total no. of ways will be
@Puneet, you are right but we can have only n-1 dividers.
On Wed, Aug 17, 2011 at 4:15 PM, Puneet Goyal puneetgoya...@gmail.comwrote:
I think it should be 2^n -1
Explanation
We can visualize it as n balls are placed and we have to place some
dividers (max=n) in betweek to divide them into
+1 nitin
there must be n-1 dividers
On Wed, Aug 17, 2011 at 4:15 PM, Puneet Goyal puneetgoya...@gmail.comwrote:
I think it should be 2^n -1
Explanation
We can visualize it as n balls are placed and we have to place some
dividers (max=n) in betweek to divide them into groups.
If we choose
Actually it was one of the assignments given to me in lab.. here is the code
#include iostream.h
#include conio.h
using namespace std;
int a[20][20][20]; // Global declration to make every cell's default value
to zero
// 3D matrix to implement the algorithm
void combinations(int number) //
20 matches
Mail list logo
