Re: [algogeeks] Re: question
@sateesh
suppose after sorting the array is
-99,-98,-97,-96,-95,-2,-1,0,4,5,99
the answer should be {-99,0,99}.. sum is closest to zero here
so i dnt think the transition method works
On Fri, May 7, 2010 at 9:58 PM, sateesh sateeshk...@gmail.com wrote:
I think this can be solved in better way.
1) Store the copy of array to get the indexes for the elements at the
end of algo
2) Sort the array time: O(nlogn), space: O(1)
3) If first element of array is -ve and last element of array is not -
ve, find the element at
which -ve to +ve transition happens
ex: -a -b +c +d
check the absolute minimum of following combinations and pick
the correct pair
-b+c+d
-a+c+d
-a-b+c
-a-b+d
here I assumed two +ve, two -ve. If only one -ve or one +v
exists, we can pick the correct 3 elements straight away
else if all are -ve numbers , pick last 3 elements
else pick first 3 elements
This total process takes O(n) time
4) Based on picked three elements, do linear search on copied array
to get there indexes.
time: O(n)
Overall it takes O(nlogn) time complexity and O(n) space complexity.
Do you guys find any flaw in it ?
-Sateesh
IIT Kanpur 2004 M.Tech CSE Batch.
On May 4, 10:43 pm, Afroz Mohiuddin afrozena...@gmail.com wrote:
Well if you want a sum of exactly 0 (or any constant) , there is an
O(N^2)
way
Take your array, and hash it, note that it is always possible to hash a
static set of keys so that the search/find in it is worst case O(1). This
takes O(N) space, and time.
Then over all the tuples of numbers in the original array (a,b) check if
0 -
(a+b) is there in the hash set, time complexity O(N*N).
For closest to 0 I guess the above solution is good.
On Mon, May 3, 2010 at 2:18 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com
wrote:
given an array(unsorted) may contain negative numbers too
find the index of three numbers whose sum is closest to zero in O(N2
log
N) time and O(N) space.
P.S -3 is more close to zero then -6 (number line ...)
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
We are here on earth to do good for others. What the others are here for,
I
don't know.
Afroz Mohiuddin
Final Year Masters Student
Dept Computer Science and Engineering
Indian Institute of Technology Kanpur
Kanpur - 208016
INDIA
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group athttp://
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: Complexity of Algorithms
A program is just an implementation of an algorithm. You may use any language to implement an algorithm as a program. To make time and space complexity analysis independent of language or computing platform, we relate them with algorithm. This is also useful when you need to compare different solutions to same problem without bogging down by programming language constructs . That is why its a good practice to write algorithms in pseudo programming language and do the complexity analysis and then perform comparison, otherwise its simply impossible to do complexity analysis of all possible implementations of the algorithm. Book by Thomas cormen is bible of algorithms, but is too big and not easy to read. The other book that I had suggested has possibly the best possible explanations of concepts at undergraduate level. I havent come across any other books better then these two. There is one more book which is slightly more basic and is easier to read : Analysis of Algorithms, Jones Barlett Publications On Sat, May 8, 2010 at 5:18 PM, scanfile rahul08k...@gmail.com wrote: sorry for replying after a long hours. @varun thanx for great tutorialbut still i'm confused in the complexity concept of algorithm. I do not understand that complexity is for the algorithms or for programs. On May 8, 11:20 am, Ralph Boland rpbol...@gmail.com wrote: On May 5, 7:59 am, Varun Nagpal varun.nagp...@gmail.com wrote: Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. For data structures there is often three complexities. 1) Time to build the data structure. (e.g. build a balance binary tree in linear time). 2) Space required by data structure. (e.g. tree requires linear space). 3) Time to use the data structure to gather some piece of information. (e.g. find leaf node from root node in O(log n) time. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. I tend to think average case is more important than worst case. Which is more important: the average case for quicksort or the worst case for quicksort? One of the reasons once sees worst case analysis much more than average case analysis is that average case analysis is usually much harder to do, for example the worst case and average case analysis of
Re: [algogeeks] tree from linked list
thanks a lot to all for their replies..
On 9 May 2010 11:23, rahul rai raikra...@gmail.com wrote:
can anyone give me links to more educative and active groups like algogeeks
On Sun, May 9, 2010 at 2:11 AM, Arun prasath
aruntendulkar2...@gmail.com wrote:
This does not create a balanced tree but ensures that every element in
the
tree is accessible by lg(n) time.
Time : Complexity O(n)
[a...@91blore-srv1 ~]$ cat recursion.c
#include stdlib.h
#includeunistd.h
#include stdio.h
#define TEST2
#ifdef TEST1
int arr[] = { 1,2,3,4,5,6,7};
int max_elems = sizeof(arr)/sizeof(arr[0]);
#endif
#ifdef TEST2
int arr[] = { 1,2,3,4,5};
int max_elems = sizeof(arr)/sizeof(arr[0]);
#endif
#ifdef TEST3
int arr[] = { 1,2,3,4,5,6,7,8};
int max_elems = sizeof(arr)/sizeof(arr[0]);
#endif
#define LIST_EMPTY -1
struct tree {
int data;
struct tree * left,* right;
};
struct tree* function( int , int);
void print_inorder( struct tree *);
int return_next_from_list(void)
{
static int nxt_elem = 0;
if(nxt_elem max_elems)
return arr[nxt_elem++];
return LIST_EMPTY;// empty condition
}
int main()
{
unsigned int x = max_elems;
struct tree* head;
while( x (x - 1) ) {
x = x (x - 1) ;
}
head = function(0, x);
print_inorder(head);
free(head);
return 0;
}
struct tree* function(int mid, int i)
{
int val = mid + i ;
if (val 1) {
struct tree * leaf = malloc( sizeof(struct tree) );
leaf-left = leaf-right = NULL;
leaf-data = return_next_from_list();
if(leaf-data == LIST_EMPTY) {
free(leaf);
return NULL;
}
return leaf;
}
struct tree *non_leaf = malloc( sizeof(struct tree) ) ;
non_leaf-left = function( mid, i/2);
non_leaf-data = return_next_from_list();
if (non_leaf-data == LIST_EMPTY) {
struct tree *tmp = non_leaf-left;
free(non_leaf);
return tmp;
}
non_leaf-right = function( mid+i, i/2);
return non_leaf;
}
void print_inorder( struct tree* root)
{
struct tree * trav = root;
if (!trav) {
return;
}
print_inorder(trav-left);
if(trav-left)
free(trav-left);
printf({%d}, trav-data);
print_inorder(trav-right);
if(trav-right)
free(trav-right);
}
[a...@91blore-srv1 ~]$
On Sun, May 2, 2010 at 6:38 PM, divya sweetdivya@gmail.com wrote:
u are given a sorted lnked list construct a balanced binary search
tree from it.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] 400!
thanx to all 4 the solutions..
On 3 May 2010 18:39, Varun Nagpal varun.nagp...@gmail.com wrote:
@Rajesh gave a simple elegant solution.
A look at a Linux calculator : you can even calculate 99! =
8.854887824e+5584950 in few seconds. I just looked at the code(its open
source right!), which is not so easy to understand in few minutes.
Here is the some part of code I extracted from source files:
/* Size of the multiple precision values */
#define MP_SIZE 1000
/* Base for numbers */
#define MP_BASE 1
/* Object for a high precision floating point number representation
*
* x = sign * (MP_BASE^(exponent-1) + MP_BASE^(exponent-2) + ...)
*/
typedef struct
{
/* Sign (+1, -1) or 0 for the value zero */
int sign; //, im_sign;
/* Exponent (to base MP_BASE) */
int exponent; //, im_exponent;
/* Normalized fraction */
int fraction[MP_SIZE]; //, im_fraction[MP_SIZE];
} MPNumber;
void mp_factorial(const MPNumber *x, MPNumber *z)
{
int i, value;
/* 0! == 1 */
if (mp_is_zero(x)) {
mp_set_from_integer(1, z);
return;
}
if (!mp_is_natural(x)) {
/* Translators: Error displayed when attempted take the factorial
of a fractional number */
mperr(_(Factorial is only defined for natural numbers));
mp_set_from_integer(0, z);
return;
}
/* Convert to integer - if couldn't be converted then the factorial
would be too big anyway */
value = mp_cast_to_int(x);
mp_set_from_mp(x, z);
for (i = 2; i value; i++)
mp_multiply_integer(z, i, z);
}
mp_multiply_integer(z, i, z) subroutine is too big too put in here, too see
its code visit: http://live.gnome.org/Gcalctool
http://live.gnome.org/Gcalctool
On Mon, May 3, 2010 at 2:34 PM, Anil C R cr.a...@gmail.com wrote:
@Jitendra
but that's no fun [?]
-
Anil
On Mon, May 3, 2010 at 5:12 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@siddharth and prasoon either design a very long integer library
yourself, or use gmp library in cpp or BigInteger Class in java.
Regards,
vignesh
On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:
But is there any way to accomplish this without an array ? Even for
100!.
On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:
I think challenge here is not the Execution time, but the storage. 300
! or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will
ultimately be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of
storage.
On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
I agree with abhijith. But given some very large x for which i would
have to find factorial.
I would either
(i) use gmp in cpp or BigInteger or java if its not a lab exercise or
an interview
(ii) use simple brute multiplication algorithm.
The second approach requires
(a) The no. of digits in n! for making storage available
(b) The calculation itself which I would brute force
References:
http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html
http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm
On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
google it... u will gt it
i am on mobile... cannot explain now..
On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail
On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
@divya use tail recursion and rest should be fine..
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
http://www.cse.iitb.ac.in/%7Erohitfeb14
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 400!
@jitendra: your python code is awesome and it works.:)
On Wed, May 12, 2010 at 6:37 PM, divya jain sweetdivya@gmail.comwrote:
thanx to all 4 the solutions..
On 3 May 2010 18:39, Varun Nagpal varun.nagp...@gmail.com wrote:
@Rajesh gave a simple elegant solution.
A look at a Linux calculator : you can even calculate 99! =
8.854887824e+5584950 in few seconds. I just looked at the code(its open
source right!), which is not so easy to understand in few minutes.
Here is the some part of code I extracted from source files:
/* Size of the multiple precision values */
#define MP_SIZE 1000
/* Base for numbers */
#define MP_BASE 1
/* Object for a high precision floating point number representation
*
* x = sign * (MP_BASE^(exponent-1) + MP_BASE^(exponent-2) + ...)
*/
typedef struct
{
/* Sign (+1, -1) or 0 for the value zero */
int sign; //, im_sign;
/* Exponent (to base MP_BASE) */
int exponent; //, im_exponent;
/* Normalized fraction */
int fraction[MP_SIZE]; //, im_fraction[MP_SIZE];
} MPNumber;
void mp_factorial(const MPNumber *x, MPNumber *z)
{
int i, value;
/* 0! == 1 */
if (mp_is_zero(x)) {
mp_set_from_integer(1, z);
return;
}
if (!mp_is_natural(x)) {
/* Translators: Error displayed when attempted take the factorial
of a fractional number */
mperr(_(Factorial is only defined for natural numbers));
mp_set_from_integer(0, z);
return;
}
/* Convert to integer - if couldn't be converted then the factorial
would be too big anyway */
value = mp_cast_to_int(x);
mp_set_from_mp(x, z);
for (i = 2; i value; i++)
mp_multiply_integer(z, i, z);
}
mp_multiply_integer(z, i, z) subroutine is too big too put in here, too
see its code visit: http://live.gnome.org/Gcalctool
http://live.gnome.org/Gcalctool
On Mon, May 3, 2010 at 2:34 PM, Anil C R cr.a...@gmail.com wrote:
@Jitendra
but that's no fun [?]
-
Anil
On Mon, May 3, 2010 at 5:12 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@siddharth and prasoon either design a very long integer library
yourself, or use gmp library in cpp or BigInteger Class in java.
Regards,
vignesh
On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:
But is there any way to accomplish this without an array ? Even for
100!.
On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:
I think challenge here is not the Execution time, but the storage. 300
! or 400! should generally go beyond the storage capabilities of long
long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will
ultimately be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of
storage.
On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
I agree with abhijith. But given some very large x for which i would
have to find factorial.
I would either
(i) use gmp in cpp or BigInteger or java if its not a lab exercise or
an interview
(ii) use simple brute multiplication algorithm.
The second approach requires
(a) The no. of digits in n! for making storage available
(b) The calculation itself which I would brute force
References:
http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html
http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm
On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
google it... u will gt it
i am on mobile... cannot explain now..
On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail
On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
@divya use tail recursion and rest should be fine..
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
http://www.cse.iitb.ac.in/%7Erohitfeb14
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
