[algogeeks] Re: String- Anagrams.

[Ramaswamy R]

This requires lexicographic permutations.
http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation
This should be a good starting point - http://geeksforgeeks.org/?p=767.

On Sun, Aug 30, 2009 at 12:32 AM, Nagendra Kumar wrote:

>
> Write a method to print all valid anagrams of a string
>
> -Nagendra
>
> >
>


-- 
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).

http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: possible in logn

[Ramaswamy R]

On Tue, Sep 1, 2009 at 5:58 AM, ankur aggarwal wrote:

> it is a jus a try
>
> i=1,j=2;
> while (a[i] {
>j=i;
>i=i*2;
> }
>
> now we have i and j and we know that in between these indexes we have a
> point z (n as u say) where
>

Not necessarily. The problem only states that the 1st n elements are sorted.
Not that the the 1st n elements are the least of those in the array.

So if every element at even location is greater than the previous, then the
n need not fall withing [i, j].


>
> a[z-1] and a[z]>[z+1]
>
> now apply the abive procedure between i and j
>
> (its like binary search)
>
> eg  we have m=50 and let n=24 (we dont know this value)
>
> then for i=16 and j=32 this condition will break ..
> now apply this logic in between 16 and 32.
> if u find z(or say n) then we can find x easily..
> i think i made my logic clear..
>
> comment plz .
>
>
> >
>


-- 
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).

http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: possible in logn

[Ramaswamy R]

It is possible.
This will be a binary search as well. Only instead of matching the value
with the mid value you'd check the following

bool c1 = array[left] < array[mid]
bool c2 = array[mid] < array[right]

if both the conditions are true then, then the entire range is sorted
if c1 is true and c2 is NOT true, then search for it in mid<->right range
else
search for it in left <-> mid

Just like in binary search we'd reduce the problem space by 2 in every step
resulting in O(log N) complexity.

On Mon, Aug 31, 2009 at 9:18 AM, shashi @mnnit <
shashikantkoshta1...@gmail.com> wrote:

>
> there is an array with m elements...
>
> it is known that first n elements are sorted... but dont know what is
> 'n' n<
> given an element x find whether x is there in sorted elements.
>
> Can this be done in O(log n)??
>
> >
>


-- 
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).

http://sites.google.com/site/ramaswamyr

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: adobe interview question

[ankur aggarwal]

1 or 2
depends if diagonal sqaure are considered to be same as adjacent


On Wed, Sep 2, 2009 at 8:28 PM, Nagendra Kumar wrote:

>
> Can anyone recheck and rephrase the question becuase i think it would
> be always '0'
>
>
> On Wed, Sep 2, 2009 at 10:40 AM, Nayn wrote:
> >
> > Guys, We are anticipating an algorithm here.
> >
> > The input would be an array containing 0/1 representing black and
> > white boxes.
> >
> > On Sep 1, 8:37 pm, yash  wrote:
> >> Given a chessboard in which u dont know how the black and white boxes
> >> are arranged but this is sure that there will 32 black squares and 32
> >> white squares.You have to find the least possible disatnce between any
> >> two sqaures of same colour ...
> >
> > >
> >
>
> >
>

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[ankur aggarwal]

@vivek

check the 2nd reply of varun
he acccept his

any thought better than nlogn


On Wed, Sep 2, 2009 at 3:00 PM, Vivek S  wrote:

> @Varun S VIt wont work for this 1 3 4 5
>
> 2009/9/2 Varun S V 
>
>> Since we difference between two minumum elements should suffice, how about
>> finding the min and second minimum element in the array in single scan and
>> returning their difference. This should take not more than O(N) time.
>>
>> Regards,
>> -Varun.
>>
>>
>> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 
>> <1987.shis...@gmail.com>wrote:
>>
>>> Sort the array and find the minimum of difference of adjacent values of
>>> the sorted array.
>>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>>
>>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal >> > wrote:
>>>
 given  a array of length n. find  2 number such that their differnce is
 minimum.





>>>
>>>
>>> --
>>> Shishir Mittal
>>> Ph: +91 9936 180 121
>>>
>>>
>>>
>>>
>>
>>
>>
>
>
> --
> "Reduce, Reuse and Recycle"
> Regards,
> Vivek.S
>
> >
>

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: adobe interview question

[Nagendra Kumar]

Can anyone recheck and rephrase the question becuase i think it would
be always '0'


On Wed, Sep 2, 2009 at 10:40 AM, Nayn wrote:
>
> Guys, We are anticipating an algorithm here.
>
> The input would be an array containing 0/1 representing black and
> white boxes.
>
> On Sep 1, 8:37 pm, yash  wrote:
>> Given a chessboard in which u dont know how the black and white boxes
>> are arranged but this is sure that there will 32 black squares and 32
>> white squares.You have to find the least possible disatnce between any
>> two sqaures of same colour ...
>
> >
>

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: Median Finding algorithms.

[Dufus]

Nice :-)
That doesnt even require O(k) extra space.

_dufus

On Sep 1, 8:36 pm, Shishir Mittal <1987.shis...@gmail.com> wrote:
> @Nagendra : As earlier told Refer Pg 189, Cormen, an algorithm is given  to
> find the Kth largest element in O(n) *worst* time complexity.
>
> @Dufus: yeah, am pretty sure that the algorithm I have described results in
> K closest elements to median.
> For e.g. Let the array be 2 5 7 10 11 14 19 45 121 i.e. n= 9 elements and 5
> closest medians are required.
>
> First determine the median in O(n) time using  Linear general selection
> algorithm - "Median of Medians
> algorithm"by
> looking for 5th largest element in the array.
> Median = 11.
>
> int compare (int a, int b, int median){
>    return ( abs(median - a) - abs(median - b)) ;}
>
> Rest of the task is similar to first  finding the (k)th  smallest element in
> the array
> |2-11|, |5-11|, |7-11|, |10-11|, |11-11|, |14-11|, |19-11|, | 45-11|,
> |121-11|
> i.e. 9, 6, 4, 1, 0, 3, 8, 34, 110
> and then partitioning the array around the pivot and returning the first k
> elements as the solution.
> Storing the above array in O(n) space and then performing the task would
> have ease the task but if space is a constraint (constant space), compare
> function described above can be used.
>
> Working for constant space,
> Using the compare function, let ** the first recursive call SELECT(arr, 0,
> 8, 5) *for e.g* does partitioning for index 2.
> The partitioned array for pivot arr[2] = 7 is
> (10, 11, 14) 7 (2, 5, 19, 45, 121)  (order of elements in the bracket may
> vary depending upon coding).
> equivalent to (1, 0, 3,) 4 ( 9, 6, 8, 34, 110) for O(n) space case.
> so 7 is the 4th smallest element.
>
> the above calls SELECT (arr, 4, 8, 5 - 4)
> which *ultimately* partitions the array into
> (10 , 11, 14, 7,) 5 (2, 19, 45, 121)
> equivalent to (1, 0, 3, 4,) 6 ( 9, 8, 34, 110) for O(n) space case.
>
> the first 5 elements is the required answer.
>
> Overall worst case time complexity : O(n), space complexity : O(1).
> O(n) space simplifies the coding and understanding of the problem.
>
> On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal 
> wrote:
>
> > @shishir
>
> > i could understand
> > cann u give an example..
>
> --
> Shishir Mittal
> Ph: +91 9936 180 121

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Vivek S]

@Varun S VIt wont work for this 1 3 4 5

2009/9/2 Varun S V 

> Since we difference between two minumum elements should suffice, how about
> finding the min and second minimum element in the array in single scan and
> returning their difference. This should take not more than O(N) time.
>
> Regards,
> -Varun.
>
>
> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> Sort the array and find the minimum of difference of adjacent values of
>> the sorted array.
>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>
>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
>> wrote:
>>
>>> given  a array of length n. find  2 number such that their differnce is
>>> minimum.
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>>
>>
>
> >
>


-- 
"Reduce, Reuse and Recycle"
Regards,
Vivek.S

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: Find longest palindrom in a give n string in O(N)

[nitin mathur]

Hi everybody..

I am sorry as the algorithm I proposed takes O(n^2) and not O(n). But its
not wrong.

@Ankur The algorithm given in cormen is for longest common
subsequence. But a similar algorithm exists for longest common substring
too.

you can find it following the link
http://en.wikipedia.org/wiki/Longest_common_substring_problem

Actually
these problems (that uses Dynamic Programming approach) are solved in two
stages. First, we need to build a table and then we need to traverse it in
particular fashion to retrieve all possible longest common substrings.

The second stage takes O(n) time.
But the preprocessing takes O(n^2) time.
So, overall it takes O(n^2) time.

I believe its worst approach for this problem (as it needs O(n^2) extra
spaces too). So not needed to discuss more about this approach. Better some
other method should be discovered.



Nitin Mathur

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Prashant]

Hi,
I think we can use Min Heap Algorithm right!


On Wed, Sep 2, 2009 at 3:03 PM, Varun S V  wrote:

> Sorry this doesnt work. The difference between any other two sets can be
> lesser than the difference between two min numbers.
>
>
> On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:
>
>> Since we difference between two minumum elements should suffice, how about
>> finding the min and second minimum element in the array in single scan and
>> returning their difference. This should take not more than O(N) time.
>>
>> Regards,
>> -Varun.
>>
>>
>> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 
>> <1987.shis...@gmail.com>wrote:
>>
>>> Sort the array and find the minimum of difference of adjacent values of
>>> the sorted array.
>>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>>
>>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal >> > wrote:
>>>
 given  a array of length n. find  2 number such that their differnce is
 minimum.





>>>
>>>
>>> --
>>> Shishir Mittal
>>> Ph: +91 9936 180 121
>>>
>>>
>>>
>>>
>>
>
> >
>


-- 
Regards,
Prashant Kulkarni

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: adobe interview question

[Nayn]

Guys, We are anticipating an algorithm here.

The input would be an array containing 0/1 representing black and
white boxes.

On Sep 1, 8:37 pm, yash  wrote:
> Given a chessboard in which u dont know how the black and white boxes
> are arranged but this is sure that there will 32 black squares and 32
> white squares.You have to find the least possible disatnce between any
> two sqaures of same colour ...

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Bharath]

If the range of numbers is known, sort the array using radix sort and
compare difference of adjacent elements.

On Sep 2, 2:33 pm, Varun S V  wrote:
> Sorry this doesnt work. The difference between any other two sets can be
> lesser than the difference between two min numbers.
>
> On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:
>
> > Since we difference between two minumum elements should suffice, how about
> > finding the min and second minimum element in the array in single scan and
> > returning their difference. This should take not more than O(N) time.
>
> > Regards,
> > -Varun.
>
> > On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 
> > <1987.shis...@gmail.com>wrote:
>
> >> Sort the array and find the minimum of difference of adjacent values of
> >> the sorted array.
> >> Time Complexity : O(nlogn), Space Complexity : O(1)
>
> >> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
> >> wrote:
>
> >>> given  a array of length n. find  2 number such that their differnce is
> >>> minimum.
>
> >> --
> >> Shishir Mittal
> >> Ph: +91 9936 180 121

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Amit Chauhan]

It won't work for following case

If suppose array contains the following integers
10 5 1 15 9
then according to you answer would be diff = |1-5| = 4
but correct answer is diff = |9-10| = 1

Thanks and Regards

Amit Chauhan
http://web.iiit.ac.in/~chauhan
Mobile : +91-9966347645

Y! IM   :  amitc_...@yahoo.co.in
GTalk  : amitchauhan@gmail.com



  There is always, always, always something to be thankful for !!

Sent from Hyderabad, AP, India
Ogden Nash   -
"The trouble with a kitten is that when it grows up, it's always a cat."

On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:

> Since we difference between two minumum elements should suffice, how about
> finding the min and second minimum element in the array in single scan and
> returning their difference. This should take not more than O(N) time.
>
> Regards,
> -Varun.
>
>
> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> Sort the array and find the minimum of difference of adjacent values of
>> the sorted array.
>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>
>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
>> wrote:
>>
>>> given  a array of length n. find  2 number such that their differnce is
>>> minimum.
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>>
>>
>
> >
>

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: N-Ary Tree and Resource management

[Geoffrey Summerhayes]

On Aug 29, 2:05 pm, nagendra kumar  wrote:
> Given a n-ary tree of resources arranged hierarchically. A process
> needs to lock a resource node in order to use it. But,
>  A node cannot be locked if any of its descendant or ancestor is
> locked.
> I was supposed to
> -> write the structure of node
> -> write codes for
> -> islock()- returns true if a given node is locked and false if it is
> not
> -> lock()- locks the given node if possible and updates lock
> information
> -> unlock()- unlocks the node and updates information.
> Codes should be :
> Islock –O(1)
> Lock()- O(log n)
> unLock()- O(log n)

I'd go with

struct node
{
node *descendants[n];
node *lockingElement;
node *parent;
bool isLock(){return lockingElement!=null;}
void Lock()
{
   LockParent(this);
   foreach(node * n in descendants) n->LockChildren(this);
}
void Unlock() // because unlock isn't two words
{
   // gets messy if you allow arbitrary nodes to be unlocked
   if(lockingElement!=this)throw;
   UnlockParent();
   foreach(node * in descendants) n->UnlockChildren();
}
void LockParent(node *locker)
{
lockingElement=locker;
if(parent!=null) parent->LockParent(locker);
}
void UnlockParent()
{
lockingElement=null;
if(parent!=null) parent->UnlockParent();
}
void LockChildren(node *locker)
{
lockingElement=locker;
foreach(node *n in descendants) n->LockChildren(locker);
}
void UnlockChildren(node *locker)
{
lockingElement=null;
foreach(node *n in descendants) n->UnlockChildren(locker);
}
}

untested and coded on the fly UAYOR

--
Geoff

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[dinesh bansal]

While sorting itself, algorithm can keep track of minimum difference between
two consecutive elements found so far and the elements. This way time
complexity is same as time complexity of sorting algorithm.

Space complexity also I think its O(1).



On Wed, Sep 2, 2009 at 6:00 PM, Ralph Boland  wrote:

>
>
>
> On Sep 1, 7:05 am, ankur aggarwal  wrote:
> > given  a array of length n. find  2 number such that their differnce is
> > minimum.
>
> As already pointed out sorting and then comparing adjacent elements
> gives you an O(n log n) algorithm.
> If you have a likelyhood of duplicates then heapsort might be better
> since the heap can be built in linear time and the sort phase can be
> aborted if a duplicate element is found.  Alternatively one could
> put your elements into a set (using hashing) and stop immediately
> if you discover a duplicate by adding an element to the set that is
> already there (O(n) expected time to build the set).
>
> Ralph Boland
> >
>


-- 
Dinesh Bansal
The Law of Win says, "Let's not do it your way or my way; let's do it the
best way."

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Ralph Boland]

On Sep 1, 7:05 am, ankur aggarwal  wrote:
> given  a array of length n. find  2 number such that their differnce is
> minimum.

As already pointed out sorting and then comparing adjacent elements
gives you an O(n log n) algorithm.
If you have a likelyhood of duplicates then heapsort might be better
since the heap can be built in linear time and the sort phase can be
aborted if a duplicate element is found.  Alternatively one could
put your elements into a set (using hashing) and stop immediately
if you discover a duplicate by adding an element to the set that is
already there (O(n) expected time to build the set).

Ralph Boland
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Geoffrey Summerhayes]

On Sep 1, 8:02 pm, Ramaswamy R  wrote:
> Brute force, pick all combinations and keep track of minimum difference.
> Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
> A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
> adjacent pairs and find the minimum difference. Complexity O(nlog n).
>

Could modify the sort to keep track of the minimum distance during
comparison, if two numbers have the minimum distance the sort must
compare them at some point.

--
Geoff
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Varun S V]

Sorry this doesnt work. The difference between any other two sets can be
lesser than the difference between two min numbers.

On Wed, Sep 2, 2009 at 2:57 PM, Varun S V  wrote:

> Since we difference between two minumum elements should suffice, how about
> finding the min and second minimum element in the array in single scan and
> returning their difference. This should take not more than O(N) time.
>
> Regards,
> -Varun.
>
>
> On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:
>
>> Sort the array and find the minimum of difference of adjacent values of
>> the sorted array.
>> Time Complexity : O(nlogn), Space Complexity : O(1)
>>
>> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
>> wrote:
>>
>>> given  a array of length n. find  2 number such that their differnce is
>>> minimum.
>>>
>>>
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>> >>
>>
>

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: minimum difference.

[Varun S V]

Since we difference between two minumum elements should suffice, how about
finding the min and second minimum element in the array in single scan and
returning their difference. This should take not more than O(N) time.

Regards,
-Varun.

On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal <1987.shis...@gmail.com>wrote:

> Sort the array and find the minimum of difference of adjacent values of the
> sorted array.
> Time Complexity : O(nlogn), Space Complexity : O(1)
>
> On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal 
> wrote:
>
>> given  a array of length n. find  2 number such that their differnce is
>> minimum.
>>
>>
>>
>>
>>
>
>
> --
> Shishir Mittal
> Ph: +91 9936 180 121
>
>
> >
>

--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---