Female Coding Pioneer
Ada Lovelace, the first programmer and a visionary mathematician, was chiefly known for her work on Charles Babbage's proposed mechanical general-purpose computer, the Analytical Engine. She was fond of sequences. During her studies she came across an infinite sequence that was generated using the following algorithm, starting with an empty sequence.
Starting from step number 1, in step number i, the integer i is appended to the sequence exactly k times where k is equal to the number of set bits in i.
Given an array query of n integers, for each query, find the value at the given index of the array assuming indexing starts at 0. Report an array of n integers where the xth integer represents the answer to the xth query.
Example
Given, n = 2 and query = [4, 10], the sequence is generated as follows.
Step Number | Binary Representation of Number | Number of set bits in Number | Sequence |
---|---|---|---|
1 | 1 | 1 | [1] |
2 | 10 | 1 | [1, 2] |
3 | 11 | 2 | [1, 2, 3, 3] |
4 | 100 | 1 | [1, 2, 3, 3, 4] |
5 | 101 | 2 | [1, 2, 3, 3, 4, 5, 5] |
6 | 110 | 2 | [1, 2, 3, 3, 4, 5, 5, 6, 6] |
7 | 111 | 3 | [1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 7] |
In the generated sequence, the value at index 4 is 4, and at index 10 is 7. Hence the answer is [4, 7].
Function Description
Complete the function getValueAtIndices in the editor below.
getValueAtIndices takes the following arguments:
int queries[n]: the queries
Returns
int[n]: the answers to the queries
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ query[i] ≤ 109
Input Format For Custom Testing
The first line contains an integer n, the number of elements in queries.
Each of the next n lines contains an integer, queries[i].Sample Case 0
Sample Input For Custom Testing
STDIN FUNCTION ----- -------- 3 → queries[] size n = 3 2 → queries = [2, 3, 6] 3 6
Sample Output
3 3 5
ExplanationIn the generated sequence [1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 7], the values at indices 2, 3, and 6 are 3, 3, and 5.Sample Case 1
Sample Input For Custom Testing
STDIN FUNCTION ----- -------- 3 → queries[] size n = 3 5 → queries = [5, 0, 5] 0 5
Sample Output
5 1 5
ExplanationThe generated sequence is [1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 7].Language
C++14
#include <bits/stdc++.h>
/*
* Complete the 'getValueAtIndices' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts INTEGER_ARRAY query as parameter.
*/
vector<int> getValueAtIndices(vector<int> query) {
}
int main()
Comments
Post a Comment