Given an Array \(arr\) of length \(N\) find the index (0-indexed) of previous co-prime element for each index \(0 \le i < N\), or \(-1\) if there's no such value.
Two values \(x\) and \(y\) are called co-prime if \(GCD(x, y) = 1\).
Previous co-prime element of \(arr[i]\) is the first element co-prime to \(arr[i]\) on the left of index \(i\), ie. maximum \(j\) such that \(GCD(arr[i], arr[j]) = 1\) and \(j < i\), or -1 if there's no co-prime element to the left of \(arr[i]\).
NOTE:
- Use of Fast I/O is recommended for this problem.
Input Format:
- First line contains an integer \(T\) denoting the number of test cases.
- First line of each testcase contains an integer \(N\) denoting length of \(arr\).
- Next line contains \(N \) space-seperated integer, denoting the elements of \(arr\).
Output Format:
- For each testcase, In a single line, print the index of previous co-prime element of \(arr[i]\) for each index \(0 \le i < N\), or \(-1\) if no such value.
Constraints:
- \(1 \le T \le 10\)
- \(1 \le N \le 10^5\)
- \(1 \le arr[i] \le 10^5\)
5 4 2 4 3 9 5 1 2 3 4 5 6 3 6 9 1 2 3 7 1 2 1 2 1 2 1 8 5 2 4 6 11 13 26 39
-1 -1 1 1 -1 0 1 2 3 -1 -1 -1 2 3 4 -1 0 1 2 3 4 5 -1 0 0 0 3 4 4 4
In third testcase, \(arr = [3, 6, 9, 1, 2, 3]\)
First, Second and Third element has no co-prime element to left, hence \(-1\) is their previous index.
Fourth element is co-prime to \(9\), ie. index \(2\).
Fifth element is co-prime to \(1\), ie. index \(3\).
Sixth element is co-prime to \(2\), ie. index \(4\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor