(Serendipity) A positive integer is said to be serendipitous if it survives the
ID: 3888369 • Letter: #
Question
(Serendipity) A positive integer is said to be serendipitous if it survives the follow- ing ordeal: Step 1: S1 = Z+ Step 2: Remove every 2nd number from S1, and call this set S2. Step 3: Remove every 3rd number from S2, and call this set S3, ... ... Step i: Remove every ith number from Si-1, and call this set Si, .... .... Say that S is the set of positive integers that remain after the ordeal is over. Then S is the set of all serendipitious numbers; in fact, S = {1, 3, 7, 13, 19, .....}. Your mission, should you choose to accept it, is to nd all serendipitous numbers smaller than n. Consider the following two (ideas for) algorithms. A1: Use a boolean array of length n and make repeated passes over the array, removing numbers until it completes a pass without any removals. A2: Maintain a linked list of numbers still thought to be serendipitious; at each pass shrink the list as needed, halting when a pass is completed with no removals. Analyze the runtime of A1 and A2. Suggestion: first write pseudocode (in English and readable by a human) for each algorithm.
Explanation / Answer
A1 Algorithm
Taking integer array in place of boolean array,but it will also have same complexity
int S[n+1] \ intialising the array
for( i=1 to i=n)
cin>>S[i] //getting the input
removal_number=2
while( removal_number<=n) //looping to increase removal_number from 1 to n
{
for( i= 1 to n)
{
if( i % removal_number ==0)
{
S[i]=-1 //assigning -1 to that index
}
}
//removing elements by copying only needed element in another array
j=0;
for( i=1 to n)
{
if(S[i]==-1)
temp[j++]=S[i];
}
//copying back to orginial array
for(i=1 to j)
S[i]=temp[i];
n=j//reducing the size of orginal array
removal_number++; //increment removal_number
}
//Elements left in S will be Serendipity
A2 Algorithm:
LinkedList S_head; //intialised linked list with all elements
removal_number=2
while(removal_number<=S_head.size())
{
delete_every_n_node(S_head,removal_number)//dividing every nth element in single pass
}
print S_head
Analysis of A1,A2
Both will have same time complexity of O(n^2) but A1 will have additional space complexity of O(n) for copying into new array ,while A2 wont have any additional
space complexity.
Also A1 will take more time while execution because it will copy elements to temporary array for deleting the elements and again copying back to orginial array,while
A2 wont take any of copying time as element of linked list can be deleted easily without any shifting of elements or copying into new array
SO A2 is better algorithm for above problem
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.