DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 47--------------------------------------------------
Please find the repeated element in the linked list.
By: kranthipls Date: August 22, 2012, 10:50 am
---------------------------------------------------------
[size=12pt]Given a linked list. It consists of elements 1 to n.
The total number of elements in the list are n+1. Please find
the element that is repeated in the list in linear time and
constant space complexity[/size].
NOTE: The list is not sorted.
#Post#: 56--------------------------------------------------
Re: Please find the repeated element in the linked list.
By: kranthipls Date: August 24, 2012, 11:51 pm
---------------------------------------------------------
Just add all the numbers in the linked list and the sum be X.
:-*
Now the repeated element is X - n*(n+1)/2 ;)
#Post#: 156--------------------------------------------------
Re: Please find the repeated element in the linked list.
By: kpr29 Date: November 19, 2012, 10:27 pm
---------------------------------------------------------
nice.......... :D
#Post#: 261--------------------------------------------------
Re: Please find the repeated element in the linked list.
By: satya Date: November 28, 2012, 11:31 pm
---------------------------------------------------------
The solution is good..........can anyone tell how do we know the
time n space complexities after getting the soln....(in general,
for any problem,,,,as im not so sure about these
complexities......) ??? ???
#Post#: 263--------------------------------------------------
Re: Please find the repeated element in the linked list.
By: kranthipls Date: November 28, 2012, 11:38 pm
---------------------------------------------------------
@Satya Which one do you want to know. The time or space
complexity................
#Post#: 274--------------------------------------------------
Re: Please find the repeated element in the linked list.
By: satya Date: November 30, 2012, 2:01 am
---------------------------------------------------------
both complexities............... ???
#Post#: 275--------------------------------------------------
Re: Please find the repeated element in the linked list.
By: kranthipls Date: November 30, 2012, 2:06 am
---------------------------------------------------------
Time Complexity: Just try to find the total number of cpu
operations that are going to take place and which is dependent
on input size i.e n....
Space Complexity: The total amount of space that you use in
order to perform particular function or operation......
If the amount of memory you use is not dependent on the input
size then it is space complexity is constant O(1)..........
Other wise it is not........
*****************************************************