[algogeeks] Re: minimum no. of clicks
Hi, My approach:- 3 1 2 1 4 1 2 1 4 3 2 1) Find matching element from start and end. here it willl be 3 2) Perfrom (#1) for sub array 1 2 1 4 1 2 1 4 here it will be 2 1 4 1 2 4 left out 3) Perfrom (#1) on 2 1 4 1 2 here it will be 1 4 1 4) Perform (#1) on 1 4 1 here it will be 4 5) 4 is single element. discard it. @1 Now going to discard earlier found pairs..FROM INSIDE GOING OUT 6) 11 - discard @ 2 7) 22 - discard @ 3 8) 11 - discard @ 4 9) 4 - discard @5 10) 33 - discard @ 6 11) 2 - discard @ 7 Special coding.. :- 1) Consider 1 2 1 3 1 11 - subarrray 2 1 3 sent match not found. remember... last matching element.. which is 1. delete remainging single elements. in this case...from 2 1 3 ... 2 and 3 will be deleted.. 1 1 1 will be deleted.. 3 clicks for 5 elements... On Feb 3, 1:42 am, sourabh jakhar sourabhjak...@gmail.com wrote: this solution is wrong On Wed, Feb 2, 2011 at 12:41 AM, bittu shashank7andr...@gmail.com wrote: @ its again the question related to the frequency..of number My Approach would be we have to count the no. of time the a particular number occurring in the array then first took the number which has lowest frequency in case of Tie FCFS used up. then proceed to higher frequency number that represents the continuous chunks so that how much elements this chunks it has we can remove this in a single click so on so for this 3 1 2 1 4 3 1 2 1 4 3 2 here array of 4 elements Elements 1 2 3 4 ///also lets say we are initializing the array index as 1 Index 1 2 3 4 Frequency 4 3 3 2 we first process the 4 Click Required 1 then 2 Click Required 1 then 3 Click Required 1 then 1 Click Required 1 Total Click Required =4 so It Can be done in O(n) while space O(n) is penalty we have to pay for it...more better approach will be appreciated Correct me if you Find Approach is wrongs Thanks Regrads Shashank Mani The best way to escape from a problem is to solve it. -- 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.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD 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?hl=en.
[algogeeks] Re: minimum no. of clicks
@dave ,saurabh sorry..i didn't sort the array but after sorting we can do.. Thanks Shashank -- 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: minimum no. of clicks
@Bittu: Isn't it silly to use an O(n log n) algorithm when just naively clicking on the digits in order gives an O(n) algorithm? Dave On Feb 2, 8:16 am, bittu shashank7andr...@gmail.com wrote: @dave ,saurabh sorry..i didn't sort the array but after sorting we can do.. Thanks Shashank -- 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: minimum no. of clicks
@dave u seems to b right .last post i put in hurry.. it is if provide your approach...we are eating space by commenting ..so try it. we are waiting fro your solution..still i not getting enough time ... Thanks Shashank -- 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: minimum no. of clicks
hey dave! what do you mean naively clicking O(n)? Can you explain the
exact algo?
If you read the question properly, you should realize that it requires the
minimum clicks.
Naively clicking is not going to give you minimum clicks.
On Wed, Feb 2, 2011 at 3:21 AM, Dave dave_and_da...@juno.com wrote:
@Srikar: Isn't it sort of silly to propose an O(n log n) algorithm
when just naively clicking on the digits in order gives an O(n)
algorithm?
Dave
On Feb 1, 12:04 pm, Srikar srikar2...@gmail.com wrote:
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com
wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3 making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to find
minimum number of clicks required? Another example is {1, 2, 3, 2, 1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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.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 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: minimum no. of clicks
@Srikar: You need to read what I said more carefully. An O(n log n)
algorithm was proposed. I merely pointed out that it could not be
optimal, since a trivial algorithm is O(n). I didn't say anything
about the trivial algorithm being optimal or the solution to the
problem.
Dave
On Feb 2, 12:33 pm, Srikar srikar2...@gmail.com wrote:
hey dave! what do you mean naively clicking O(n)? Can you explain the
exact algo?
If you read the question properly, you should realize that it requires the
minimum clicks.
Naively clicking is not going to give you minimum clicks.
On Wed, Feb 2, 2011 at 3:21 AM, Dave dave_and_da...@juno.com wrote:
@Srikar: Isn't it sort of silly to propose an O(n log n) algorithm
when just naively clicking on the digits in order gives an O(n)
algorithm?
Dave
On Feb 1, 12:04 pm, Srikar srikar2...@gmail.com wrote:
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com
wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3 making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to find
minimum number of clicks required? Another example is {1, 2, 3, 2, 1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2Bunsubscribe@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
- Show quoted text -
--
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.comalgogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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: minimum no. of clicks
hi,
I suppose this could be solved in O(n) time if we use hash table. although
the space complexity will increase
Thanks and regards,
Gajendra Dadheech
On Thu, Feb 3, 2011 at 12:47 AM, Dave dave_and_da...@juno.com wrote:
@Srikar: You need to read what I said more carefully. An O(n log n)
algorithm was proposed. I merely pointed out that it could not be
optimal, since a trivial algorithm is O(n). I didn't say anything
about the trivial algorithm being optimal or the solution to the
problem.
Dave
On Feb 2, 12:33 pm, Srikar srikar2...@gmail.com wrote:
hey dave! what do you mean naively clicking O(n)? Can you explain the
exact algo?
If you read the question properly, you should realize that it requires
the
minimum clicks.
Naively clicking is not going to give you minimum clicks.
On Wed, Feb 2, 2011 at 3:21 AM, Dave dave_and_da...@juno.com wrote:
@Srikar: Isn't it sort of silly to propose an O(n log n) algorithm
when just naively clicking on the digits in order gives an O(n)
algorithm?
Dave
On Feb 1, 12:04 pm, Srikar srikar2...@gmail.com wrote:
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all
of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com
wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same
numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3
making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to
find
minimum number of clicks required? Another example is {1, 2, 3, 2,
1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
- Show quoted text -
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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.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 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: minimum no. of clicks
this solution is wrong On Wed, Feb 2, 2011 at 12:41 AM, bittu shashank7andr...@gmail.com wrote: @ its again the question related to the frequency..of number My Approach would be we have to count the no. of time the a particular number occurring in the array then first took the number which has lowest frequency in case of Tie FCFS used up. then proceed to higher frequency number that represents the continuous chunks so that how much elements this chunks it has we can remove this in a single click so on so for this 3 1 2 1 4 3 1 2 1 4 3 2 here array of 4 elements Elements1 2 3 4 ///also lets say we are initializing the array index as 1 Index 1 2 3 4 Frequency 4 3 3 2 we first process the 4 Click Required 1 then 2 Click Required 1 then 3Click Required 1 then 1Click Required 1 Total Click Required =4 so It Can be done in O(n) while space O(n) is penalty we have to pay for it...more better approach will be appreciated Correct me if you Find Approach is wrongs Thanks Regrads Shashank Mani The best way to escape from a problem is to solve it. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD 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?hl=en.
[algogeeks] Re: minimum no. of clicks
@ its again the question related to the frequency..of number My Approach would be we have to count the no. of time the a particular number occurring in the array then first took the number which has lowest frequency in case of Tie FCFS used up. then proceed to higher frequency number that represents the continuous chunks so that how much elements this chunks it has we can remove this in a single click so on so for this 3 1 2 1 4 3 1 2 1 4 3 2 here array of 4 elements Elements1 2 3 4 ///also lets say we are initializing the array index as 1 Index 1 2 3 4 Frequency 4 3 3 2 we first process the 4 Click Required 1 then 2 Click Required 1 then 3Click Required 1 then 1Click Required 1 Total Click Required =4 so It Can be done in O(n) while space O(n) is penalty we have to pay for it...more better approach will be appreciated Correct me if you Find Approach is wrongs Thanks Regrads Shashank Mani The best way to escape from a problem is to solve it. -- 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: minimum no. of clicks
@Srikar: Isn't it sort of silly to propose an O(n log n) algorithm
when just naively clicking on the digits in order gives an O(n)
algorithm?
Dave
On Feb 1, 12:04 pm, Srikar srikar2...@gmail.com wrote:
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3 making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to find
minimum number of clicks required? Another example is {1, 2, 3, 2, 1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2Bunsubscribe@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
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: minimum no. of clicks
@Bittu: You said to correct you if you are wrong, so here goes. The original problem statement says that you can remove any continuous chunk of the same numbers with one click. Maybe it would have been clearer to use the word contiguous instead of continuous, but since your 4s are not adjacent to each other, it will take two clicks to remove them. And so on. Dave On Feb 1, 1:11 pm, bittu shashank7andr...@gmail.com wrote: @ its again the question related to the frequency..of number My Approach would be we have to count the no. of time the a particular number occurring in the array then first took the number which has lowest frequency in case of Tie FCFS used up. then proceed to higher frequency number that represents the continuous chunks so that how much elements this chunks it has we can remove this in a single click so on so for this 3 1 2 1 4 3 1 2 1 4 3 2 here array of 4 elements Elements 1 2 3 4 ///also lets say we are initializing the array index as 1 Index 1 2 3 4 Frequency 4 3 3 2 we first process the 4 Click Required 1 then 2 Click Required 1 then 3 Click Required 1 then 1 Click Required 1 Total Click Required =4 so It Can be done in O(n) while space O(n) is penalty we have to pay for it...more better approach will be appreciated Correct me if you Find Approach is wrongs Thanks Regrads Shashank Mani The best way to escape from a problem is to solve it. -- 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.
