Re: [algogeeks] Re: Number Theory (Power of 3 )
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 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 faster since it contains no loops. bool PowerOfThree(unsigned int n) { int powsof3[32] = {1,3,0,9,27,0,81,243,0,729,0,2187,6561,0,19683,59049,0, 177147,0,531441,1594 323,0,4782969,14348907,0,43046721, 129140163,0,387420489,0,1162261467,3486784401}; int i = if( n 16 ) ? 16 : 0; if( n (i+8) ) i += 8; if( n (i+4) ) i += 4; if( n (i+2) ) i += 2; if( n = (i+1) ) i += 1; return powsof3[i] == n; } As in the previous algorithm, the first few statements use a binary search to find the bit number of the highest order bit set. There can be at most one power of three corresponding to each high-order-bit number, so we then check to see if the input number is the only possible power of three in the table of powers of 3 that is indexed by the high-order-bit number. The zeros in powsof3[] correspond to high- order-bit numbers that have no power of three. Dave On Dec 9, 2:35 am, Gaurav Kumar gkuma...@gmail.com wrote: What if we create a base 3 number from the given number N and then check if there is only 1 bit with value 1 and all values should be 0. For example, if lets say the number is 27. Its base 3 number will be 1 0 0 0, now since there is only 1 single 1 present in this representation, it is a power of 3. Gaurav On Dec 7, 2011, at 6:03 PM, saurabh singh wrote: 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, Dec 7, 2011 at 11:54 PM, tech coder techcoderonw...@gmail.com wrote: 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 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 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. 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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at
[algogeeks] Re: Number Theory (Power of 3 )
@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 faster since it contains no loops. bool PowerOfThree(unsigned int n) { int powsof3[32] = {1,3,0,9,27,0,81,243,0,729,0,2187,6561,0,19683,59049,0, 177147,0,531441,1594 323,0,4782969,14348907,0,43046721, 129140163,0,387420489,0,1162261467,3486784401}; int i = if( n 16 ) ? 16 : 0; if( n (i+8) ) i += 8; if( n (i+4) ) i += 4; if( n (i+2) ) i += 2; if( n = (i+1) ) i += 1; return powsof3[i] == n; } As in the previous algorithm, the first few statements use a binary search to find the bit number of the highest order bit set. There can be at most one power of three corresponding to each high-order-bit number, so we then check to see if the input number is the only possible power of three in the table of powers of 3 that is indexed by the high-order-bit number. The zeros in powsof3[] correspond to high- order-bit numbers that have no power of three. Dave On Dec 9, 2:35 am, Gaurav Kumar gkuma...@gmail.com wrote: What if we create a base 3 number from the given number N and then check if there is only 1 bit with value 1 and all values should be 0. For example, if lets say the number is 27. Its base 3 number will be 1 0 0 0, now since there is only 1 single 1 present in this representation, it is a power of 3. Gaurav On Dec 7, 2011, at 6:03 PM, saurabh singh wrote: 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, Dec 7, 2011 at 11:54 PM, tech coder techcoderonw...@gmail.com wrote: 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 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 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. 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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
Re: [algogeeks] Re: Number Theory (Power of 3 )
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 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 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. 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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number Theory (Power of 3 )
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, Dec 7, 2011 at 11:54 PM, tech coder techcoderonw...@gmail.comwrote: 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 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 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. 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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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...@googlegroups.com. For more options, visit this group at
[algogeeks] Re: Number Theory (Power of 3 )
@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 Mesra http://www.facebook.com/wgpshashank http://shashank7s.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jhoet1Yl3F0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number Theory (Power of 3 )
@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 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 Mesrahttp://www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number Theory (Power of 3 )
@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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number Theory (Power of 3 )
@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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number Theory (Power of 3 )
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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number Theory (Power of 3 )
@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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number Theory (Power of 3 )
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. 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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number Theory (Power of 3 )
@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 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. 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 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 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 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 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 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 Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number Theory (Power of 3 )
@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}; int i,j=0; unsigned int m = n; for( i = 0 ; i 5 ; ++i ) { if( m powsof2[i] ) { j += powsof2[i]; m = powsof2[i]; } } return powsof3[j] == n; } The for loop determines the bit number of the highest-order bit set. The table of powers of three is indexed by the bit number of the highest bit set. Dave On Nov 28, 2:47 am, SAMMM somnath.nit...@gmail.com wrote: Given a number u have to check whether the number(N) can be expressed in the form 3^n = N i:e It can be expressed in terms of power of 3. It can be done taking log on both but I am looking an alternate approach (bit manipulation) . -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number theory
@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. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number theory
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 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number theory
+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 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. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number theory
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 (nC0+nC1+nC2..nCn)-nC0= 2^n-1 Regards, Puneet On Wed, Aug 17, 2011 at 4:05 PM, Rohit Srivastava access2ro...@gmail.comwrote: +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 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. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, Delhi --- -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number theory
@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 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 (nC0+nC1+nC2..nCn)-nC0= 2^n-1 Regards, Puneet On Wed, Aug 17, 2011 at 4:05 PM, Rohit Srivastava access2ro...@gmail.comwrote: +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 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. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, Delhi --- -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Number theory
+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 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 (nC0+nC1+nC2..nCn)-nC0= 2^n-1 Regards, Puneet On Wed, Aug 17, 2011 at 4:05 PM, Rohit Srivastava access2ro...@gmail.comwrote: +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 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. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, Delhi --- -- --- Puneet Goyal Student of B. Tech. III Year (Software Engineering) Delhi Technological University, Delhi --- -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Number theory
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) // function that accepts the number whose combination , you { int i, j, k, larg, m, n, flag; for(i=1; i=number; i++) a[i][0][0]=i; i=1; while(i=number) { // first row of each number is copied by that number // external loop to access no. whose combination are inserted flag=1; j=1; do{ //position of rows that is being modified // inner loop that will run through i for(k=0; a[j][k][0]!=0; k++) // innermost loop that will check for largest/last no. { for(larg=0; a[j][k][larg]!=0; larg++); //to check last value larg--; if(i-ja[j][k][larg]) { for(m=0; m=larg; m++) a[i][flag][m] = a[j][k][m]; a[i][flag][m] = i-j; flag++; } // comapring last value with difference // copy all existing values to current number // insert difference between numbers //increase the pointer to insert next combination } j++; }while(j=i); i++; } k=number; for(i=0; a[k][i][0]!=0; i++) { couta[k][i][0]; for(j=1; a[k][i][j]!=0; j++) cout+a[k][i][j]; // printing of all combination of number cout\n; } } int main() { int number; coutEnter the natural number: ; cinnumber; combinations(number); getch(); return 0; } //input the number whose combination you want -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/CsTCslXuC88J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.