Consider a set of n bits with the positions numbered from 1 to n. Initially all
ID: 3753423 • Letter: C
Question
Consider a set of n bits with the positions numbered from 1 to n. Initially all the bits are set to 0. These n bits are subject to modifications over n iterations as follows. At the i th iterations the bits at the positions whose ids are multiples of i are flipped, i.e. changed from 0 to 1 or vice-versa. For example, at iteration 1, bits at all positions are flipped, at iteration 2, bits at positions 2,4,6,etc. are flipped, at iteration 3, bits at positions 3,6,9, etc. are flipped. Propose an algorithm for find out, that after n such iterations how many bits will have the value 1. Note that the answer requires only how many bits, not their positions.
-Describe the rationale for the algorithm, give the pseudocode and its complexity
- Code in C
-Aim for algorithms with complexity O(k), where k is the number of digits of n
Explanation / Answer
#include<stdio.h>
//method to flip bits
void flip(int a[],int n,int m)//complexity O(n) , n is number of bits
{
int i=0;
while(i<n)
{
if(i%m==0)
{
a[i]++;
a[i] = a[i]%2;//flipping
}
i++;
}
}
//method to print bits
void print(int a[],int n)//complexity O(n)
{
int i=0;
while(i<n)
{
printf("%d",a[i]);//printing each bit
i++;
}
printf(" ");
}
int main()
{
int n;
//reading number of bits
printf("Enter number of bits :");
scanf("%d",&n);
//declaring array
int a[n];
int i=0;
//and setting all values to zero
while(i<n)a[i++]=0;
//reading number of iterations
int m;
printf("Enter number of iterations you want to perform :");
scanf("%d",&m);
//performing m flippings
int k=1;
while(k<=m)//compleixty O(m*n)
{
printf("%dth flipping :",k);
flip(a,n,k);
print(a,n); //function calling
k++;
}
return 0;
}
//compleixty for flipping: O(n)
output:
Enter number of bits :5
Enter number of iterations you want to perform :2
1th flipping :11111
2th flipping :01010
Process exited normally.
Press any key to continue . . .