Sponsored
Sponsored
This approach uses a sliding window technique to efficiently calculate the sum of required elements. By maintaining a running sum for the window and updating it as you slide, you can achieve the necessary transformation in linear time. The key is to account for the circular nature of the array using modulo operations to wrap around indices.
Time Complexity: O(n), where n is the length of the `code` array. Each element is processed once with constant-time window updates.
Space Complexity: O(1) auxiliary space (excluding the output array).
1#include <vector>
2#include <iostream>
3using namespace std;
4
5vector<int> decrypt(vector<int>& code, int k) {
6 int n = code.size();
7 vector<int> result(n, 0);
8
9 if (k == 0) return result;
10
11 int start = 1, end = k, sum = 0;
12 if (k < 0) {
13 k = -k;
14 start = n - k;
15 end = n - 1;
16 }
17
18 for (int i = start; i <= end; ++i) {
19 sum += code[i % n];
20 }
21
22 for (int i = 0; i < n; ++i) {
23 result[i] = sum;
24 sum -= code[start % n];
25 sum += code[(end + 1) % n];
26 start++;
27 end++;
28 }
29
30 return result;
31}
32
33int main() {
34 vector<int> code = {5, 7, 1, 4};
35 int k = 3;
36 vector<int> decrypted = decrypt(code, k);
37 for (int num : decrypted) {
38 cout << num << " ";
39 }
40 return 0;
41}
42
The C++ implementation leverages the sliding window approach for calculating segment sums efficiently. We dynamically update the sum as the window moves using start and end pointers. This update is done using modulo to loop back circularly.
This approach is straightforward but less efficient, involving a direct sum computation for each index by wrapping around using the modulo operator. Each element's circular context is individually recalculated, following conditions for the sign of k.
Time Complexity: O(n*k) with n as length of `code` and k an absolute value.
Space Complexity: O(1) extra space beyond output.
1function
In this JavaScript example, the solution calculates the sum by processing each index individually and adjusting it according to the value of k, while mindful of the array's loop-around with modulo calculations ensuring accurate sums.