(Programming) There are n coins numbered sequentially from 1 to n. Initially, al

Question

(Programming)

There are n coins numbered sequentially from 1 to n. Initially, all the coins are heads. You make n scans over the coins, each time starting with coin 1. On the i th scan, i = 1, 2, ...., n, you flip the coin of every i th coin; if the coin is a head, you flip it to a tail; if it is a tail, you flip it to a head. For example, after the first scan every coin is a tail; on the second scan you only flip the even-numbered coins (coin 2, coin 4, ...) to heads so that after the second scan the even coins are heads and the odd ones are tails; the third time through you flip coin 3 (a head from the first scan), flip coin 6 (a tail from the second scan), and so on. After the last scan, how many and which of them are tails?

(a) Describe a method with pseudo-code and explain why the outcome is correct.

(b) Give a time analysis on your method and wxplain why.

(c) Please write your algorithm in C/C++. The input is one line containing an integer n, the number of coins. The output will be two lines. The first line shows an integer, the number of coins which are tails. The second line presents the numbers of the coins which are tails. These numbers are separated by spaces. A running example with the input is as below.

Program Example:

Input the number of coins: 16

4

1 4 9 6

Explanation / Answer

Hi, I have expalined your problem with help of similar problem. Please read explanaion and let me know in case of any doubt.

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way:
In first walk, the person toggles every door
In second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, …
In third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, …
………
……….
In 100th walk, the person toggles 100th door.
Which doors are open in the end?

Solution:
A door is toggled in ith walk if i divides door number. For example the door number 45 is toggled in 1st, 3rd, 5th, 9th and 15th walk.
The door is switched back to initial stage for every pair of divisors. For example 45 is toggled 6 times for 3 pairs (5, 9), (15, 3) and (1, 45).
It looks like all doors would become closes at the end. But there are door numbers which would become open, for example 16, the pair (4, 4) means only one walk. Similarly all other perfect squares like 4, 9, ….
So the answer is 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100.

Pseudo Code:

1. create a char array of length N
2. Initialize each entry of above created array with 'H'
3. for i=1 to N:
4.   do
5.       j = i
6.       while j<=N
7.           flip coin (H->T or T->H)
8.           j=j+i
9..       End
10.   End
11. 0 <- count
12. for i=1 to N
13.   do:
14.       if char[i]='T'
15.           count=count+1
16.       End
17.   End
18. print count
19. Scan char array and print index if char[i] = 'T'

Time Complexity:

O(n^2)

C++ Code:

#include<iostream>
#include<stdlib.h>

using namespace std;

int main(){
  
   int N;
   cout<<"Enter number of coins: ";
   cin>>N;
  
   char *coins = new char[N+1];
   // initializing each entry with 'H' (head)
   for(int i=1; i<=N; i++)
       coins[i] = 'H';
  
   // fliping ith coins in each iteration  
   for(int i=1; i<=N; i++){
       for(int j=i; j<=N; j=j+i){
           if(coins[j] == 'H')
               coins[j] = 'T';
           else
               coins[j] = 'H';
       }
       // after each toggle it will show content of array(state of coin)
       for(int i=1; i<=N; i++)
           cout<<coins[i]<<" ";
       cout<<endl;
   }
  
   cout<<endl<<endl;
   // counting number of heads
   int count = 0;
   for(int i=1; i<=N; i++)
       if(coins[i] == 'T')
           count++;
  
   cout<<count<<endl;  
   // printing coins number
   for(int i=1; i<=N; i++)
       if(coins[i] == 'T')
           cout<<i<<" ";
   cout<<endl;
  
  
   return 0;
}

/*

Output:

T H H H T T T H H H T T T H H H
T H H T T T T T H H T H T H H T
T H H T H T T T H T T H T H T T
T H H T H H T T H T T T T H T T
T H H T H H H T H T T T T T T T
T H H T H H H H H T T T T T T H
T H H T H H H H T T T T T T T H
T H H T H H H H T H T T T T T H
T H H T H H H H T H H T T T T H
T H H T H H H H T H H H T T T H
T H H T H H H H T H H H H T T H
T H H T H H H H T H H H H H T H
T H H T H H H H T H H H H H H H
T H H T H H H H T H H H H H H T

4
1 4 9 16

*/

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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