(Serendipity) A positive integer is said to be serendipitous if it survives the

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.

I saw a solution, but I don't know how it works and how to calculate the runtime. Can anybody help me? Thanks!

A1 /l Use a boolean array of n elements to represent list of numbers. // b is an array b[1], b[2. , b[n], where each b[2] 2 true, false for 1

Explanation / Answer

Algorithm 1: Using boolean array

Pseudocode:

1. Input the number n from the user

2. Declare a boolean array of size n (b[n]). Initialize every element to true. Here if b[i] == true, then i is a serendipitous number. Otherwise it's not a serendipitous number.

3. We will traverse this array for every alternate element first, and set it's value to false. Then we will do the same for every 3rd number. Then for every fourth number and so on.

4. Finally, we will traverse the array b[] and all those indexes where value is still true, those will be the required serendipitous numbers.

5. Now the question is that when should we stop traversing the array in Step 3 ? We should stop traversing if in any particular pass, there is no element changed.

Now let's look at the C++ code below:

#include <iostream>

using namespace std;

void FindSerendipitious(int n)
{
bool *b = new bool[n]; // boolean array to hold the final result for every integer till n
int step = 2; // Initial value of step will be 2 because firstly we have to remove every 2nd number
for(int i = 0; i < n; i ++)
{
b[i] = true; //Initializing the array with true
}
int count = 0; /* This variable will keep track of when we reach the step size and we need to toggle the boolean value from true to false */
bool flag = false; /* This flag is used to indicate that whether we changed the value of at least one true to flase in a pass or not. This will help us identify that when should we stop */
while(true)
{
count = 0;
flag = false;
for(int i = 0; i<n; i++)
{
if(b[i] == true)
count = count + 1;
  
if(count == step)
{
b[i] = false;
flag = true;
count = 0;
}
}
step = step + 1; // Increment step by 1 for the next pass
if(flag == false)
break;
}
  
cout<<"Serendipitious numbers till "<<n<<" are: "<<endl;
for(int i = 0; i < n; i++)
{
if(b[i] == true)
cout<<i+1<<" ";
}
  
}

int main()
{
int n; // number of elements
cout<<"Please enter the value of n: ";
cin>>n;
  
FindSerendipitious(n); // function call to the function
  
return 0;
  
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.