Microsoft SDE Intern Interview 2026 – Infinite Sequence Elimination

Блог пользователя sj02012006

Автор sj02012006, история, 9 месяцев назад, По-английски

You are given an infinite sequence of positive integers: 1, 2, 3, 4, 5, 6, 7, 8, ...

An infinite number of operations are performed on this sequence: In the 1st operation, every 2nd element is removed. In the 2nd operation, every 3rd element of the remaining sequence is removed. In the 3rd operation, every 4th element is removed. In the i-th operation, every (i + 1)-th element is removed. These operations continue indefinitely.

You are given an integer x. Determine whether x will remain in the sequence forever or be removed at some operation.

Input : 13

1,2,3,4,5,6,7,8,9,10,11,12,13

1st operation (remove every 2nd):

1,3,5,7,9,11,13

2nd operation (remove every 3rd):

1,3,7,9,13

3rd operation (remove every 4th):

1,3,7,13

4th operation (remove every 5th): No 5th element exists

Answer: YES

Input : 17

Answer: NO

sj02012006
9 месяцев назад
12

Комментарии (12)

Написать комментарий?

Mohit-Chowdhary

9 месяцев назад, скрыть # |

-10

so in the first test we check if 13 is removed or not?

→ Ответить

i_hate_pahadans

9 месяцев назад, скрыть # |

← Rev. 3 →

-13

Nvm I was wrong

→ Ответить

i_hate_pahadans

9 месяцев назад, скрыть # ^ |

-13

Can't find any pattern just brute force it man

→ Ответить

i_hate_pahadans

9 месяцев назад, скрыть # ^ |

-13

#include <bits/stdc++.h>
using namespace std;

#define f(i,s,e) for(long long i=s;i<e;i++)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define si set<int>
#define sc set<char>

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        int position=x;
        int step=2;
        bool ok=true;
        while(position%step!=0&&step<=position){
            position-=position/step;
            step++;
        }
        if(position%step==0)cout<<"NO\n";
        else cout<<"YES\n";
        
    }


    return 0;
}

→ Ответить

MShaheer

9 месяцев назад, скрыть # |

-10

You can use sieve of Eratosthenes with some minor adjustments and It may work!

→ Ответить

justin_zed

9 месяцев назад, скрыть # |

← Rev. 2 →

https://oeis.org/A000960

Hard to tell how reasonable of an interview problem it is without the upper bound on x

→ Ответить

Abhyuday7177

9 месяцев назад, скрыть # |

← Rev. 3 →

-13

Here is one pattern that I observed which might help out.

We know that after every operation that we do, the number x can either be present in the array or it will be removed from the array.

So when will x be removed from the array? When the index of the array where x is present currently is divisible by (i+1), where i is the operation number.

But what if that index is not divisible by (i+1)? Then the index where x is present will shift leftwards. Let's say x is at some index p currently. Then if p is not divisible by (i+1), p will now shift leftwards by p/(i+1) and will essentially become p -=(p/(i+1)

We can continue doing this until p >= (i+1). Why? Cus if (i+1) becomes greater than p, p cant be divisible by (i+1)

→ Ответить

Ayush.Mishra

9 месяцев назад, скрыть # |

-10

Get the initial position of the given num, and for every operation, keep checking whether it will be deleted and if not keep updating its position.

→ Ответить

-GrandMaster-

9 месяцев назад, скрыть # |

← Rev. 2 →

Question Link : https://codeforces.me/contest/2169/problem/D1

→ Ответить

avin_ash

9 месяцев назад, скрыть # |

-9

Track the number’s position in the sequence; in each round k (starting from 2), if its position is divisible by k it gets removed, otherwise its position shifts forward by subtracting how many numbers before it were removed (position / k),and this process continues until k becomes larger than its position, at which point the number is surely to survive forever. Time Complexity = O(√x).

→ Ответить