Citrix System Inc Interview Question
Country: India
What is the logic for getting this formula 2n(1+3z) ?
Please always explain fully the logic you are following and then write code...just writing code does not helps the cause.
Does it not fail for X = 1 ,2 ,3 . The minimum it needs is 8. for(z=1;X>2n(1+3z);z++).
Minimum value of 2n(1+3z) is 8 (for n =1 and z =1 ).
@: nitin
in 1 st iteration all odds are removed
so 1 , 3, 5, 7...... are not to be considered
for any no of itertions they would have been removed
now after 1 st iteration we have
2 4 6 8 10 12 14 16
in 2nd we remove every 3 rd no.
means.... 2(1+3.x) where x varies from 0 to some no.
like 2 8 14 ....
now after 2 nd iteration left are
4 6 10 12 16 18 22 24 28.....
in 3 rd we remove every 4 th element
so we remove 4(1+3x) where x from 0 to some no.
eg...4 16 28.....
..
is that clearn now for every nth iteration
2(n-1)(1+3x) where x from 0 to some no.
@: code learner sorry dear
from 0 to ......some no.
and about the odd no.'s those are removed in the very 1 st iteration
the code i submitted is for checking even no..
is that k
actully the 4 th iteration is the 5 th one becoz the first iteration is to eliminate the alternate that is odd no..
and 2n (1+3x) for n=4 and x=1 it removes 32 and x=2 it removes 56
and not 42
Dude your algo will work fine uptil n < 4 after than it will screw things up.
Lets take a look what numbers your code is removing for first five loops.
1. 8, 14, 20, 26..
2. 16, 28, 40, 52..
3. 24, 42, 60, 78..
4. 32, 56, 80, 104..
5. 40, 70, 100, 130..
what it should remove is these numbers.
1. 2, 8, 14, 20...
2. 4, 16, 28, 40...
3. 6, 24, 42, 60...
4. 10, 36, 62, 88... and (voila).
for quick just take x = 10, itr = 4, u will understand that it's not
printing anything.
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int ceil(int n,int i)
{
if(n%i == 0)
return (n/i);
return (n/i + 1);
}
int main()
{
int i = 2;
int N,n;
scanf("%d",&N);
n = N;
while(1)
{
if(n%i == 1)
{
printf("\n%d is removed in %d iteration\n",N,i-1);
break;
}
n = n-ceil(n,i);
i++;
}
return 0;
}
Explanation: Thing to understand here is that how does position of a number in the list change from (i-1)th iteration to i th iteration.
If a number is in nth position in (i-1)th iteration and n%i == 1 then it is deleted in i-1 th iteration otherwise ceil(n/i) numbers less than it have been removed and its position in next iteration is n - ceil(n/i).
"You have a number written starting from 1 to infinitive"
Please be clear, whether its a single number containing numbers written from 1 to infinitive
or a list of numbers from 1 to infinity
#include<stdio.h>
#include<math.h>
#include<conio.h>
void main()
{
int x,y,z,w;
scanf("%d", &x);
y=(int)sqrt(2*x);
if(((y*(y+1)/2)+1)<=x);
else y=y-1;
z= (y*(y+1)/2)+y;
w=z-y-1;
if(x>=w && x<z)
printf("not deleted");
else
printf("deleted");
getch();
}
complexity O(1)
i guess this r lucky numbers....we jst have to find new position of an elemnt after every iteration if position become less than current iteration the num will never get deleted......
Isnt this the famous 100 locker puzzle?
The school has 100 lockers. One by one each student has to go the lockers and open them in the following pattern:
Student 1 opens all the lockers
Student 2 goes and closes every second locker
Student 3 goes and "changes the state" of every third locker i.e. if its open , close etc and vice versa.
Student 4 changes the state of every 4th locker.
.
.
.
.Student n changes the state of every nth locker
This goes on for all 100 students.
They have to tell which all lockers are open at the after 100th student is done with his task.
Remaining number after t iteration = n - floor(n/t) - n%t ;
Where n is the number of digits in number
So we have to solve this equation for t=1,2,3,.....
- shreyans June 26, 2012all odd no. will be removed in 1st iteration ... let say for a give no. X=45465454154654 i.e even and itr be the iteration upto which we have to say it will be removed or not then for (n=1;n<=itr;n++) { for(z=1;X>2n(1+3z);z++) { if X%(2.n(1+3z))==0; print"removed in"+ nth +"iteration"; } }