Dislike of Threes

Dislike of Threes
Codeforces easy

There are \(T\) testcases. For each test you are given a positive integer \(K\), consider the sequence of positive integers that are not divisible by \(3\) and do not end with the digit \(3\) (\(1, 2, 4, 5, 7, \dots\)). Find the \(K\)-th element of this sequence. \(K\) can be an integer from \(1\) to \(1000\).

Note

The \(K\)-th element in an array/vector V is V[K-1].

Solution

We can observe that a number x should be excluded from the sequence if it is divisible by \(3\) (x % 3 == 0) or if its last digit is \(3\) (x % 10 == 3).

To solve the problem, we can generate the sequence as follows:

  1. Create a vector \(V\) to store the sequence.
vector<int> v;
  1. Start a loop at \(1\) and Continue looping until the size of \(V\) reaches \(1000\).
  2. In each iteration, add the current number to \(V\) only if it is not divisible by \(3\) and does not end with \(3\).
for (int i = 1; v.size() < 1000; i++) {
    if (i % 3 != 0 && i % 10 != 3) {
        v.push_back(i);
    }
}

Once the sequence is generated, we can read each input \(K\) and output the \(K\)-th element from the vector \(V\).

int test_cases;
cin >> test_cases;

for (int i = 0; i < test_cases; i++) {
    int k;
    cin >> k;

    cout << v[k - 1] << endl;
}