Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

sj02012006's blog

Microsoft SDE Intern Interview 2026 – Infinite Sequence Elimination
By sj02012006, history, 9 months ago, In English

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

  • Vote: I like it
  • -22
  • Vote: I do not like it

»
9 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
9 months ago, hide # |
← Rev. 3  
Vote: I like it -13 Vote: I do not like it

Nvm I was wrong

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it -13 Vote: I do not like it

    Can't find any pattern just brute force it man

    → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it -13 Vote: I do not like it 
      #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;
}
      → Reply
»
9 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
9 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

https://oeis.org/A000960

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

→ Reply
»
9 months ago, hide # |
← Rev. 3  
Vote: I like it -13 Vote: I do not like it

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)

→ Reply
»
9 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

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.

→ Reply
»
9 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

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).

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Very similar to this problem.

→ Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The Interviewer was excepting the solution in O(1) time complexity

→ Reply