Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).
Specifically, ans is the concatenation of two nums arrays.
Return the array ans.
Example 1:
Input: nums = [1,2,1] Output: [1,2,1,1,2,1] Explanation: The array ans is formed as follows: - ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]] - ans = [1,2,1,1,2,1]
Example 2:
Input: nums = [1,3,2,1] Output: [1,3,2,1,1,3,2,1] Explanation: The array ans is formed as follows: - ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]] - ans = [1,3,2,1,1,3,2,1]
Constraints:
n == nums.length1 <= n <= 10001 <= nums[i] <= 1000program concatenate_arrays
implicit none
integer, parameter :: n = 3
integer, dimension(n) :: nums = (/ 1, 2, 1 /)
integer, dimension(2 * n) :: ans
ans = [(nums(i), i=1,n), (nums(i), i=1,n)]
print '(A,*(I0,1X))', 'ans = ', ans
end program concatenate_arraystemp.f95:8:18:
8 | ans = [(nums(i), i=1,n), (nums(i), i=1,n)]
| 1
Error: Symbol āiā at (1) has no IMPLICIT type
module concatenate_array
implicit none
contains
function concatenate(nums) result(ans)
integer, intent(in) :: nums(:)
integer :: ans(size(nums)*2)
integer :: i
do i = 1, size(nums)
ans(i) = nums(i)
ans(i+size(nums)) = nums(i)
end do
end function concatenate
end module
program concatenate_array_test
use concatenate_array
implicit none
integer, parameter :: n = 4
integer, parameter :: nums(n) = [1, 2, 1, 3]
integer :: ans(size(nums)*2)
ans = concatenate(nums)
write (*,*) "Expected:", [1, 2, 1, 1, 2, 1, 3, 3, 2, 1]
write (*,*) "Actual:", ans
end program
Expected: 1 2 1 1 2 1 3 3 2 1 Actual: 1 2 1 3 1 2 1 3
def maxValue(n, index, maxSum):
maxSum -= n
left, right, ans = 0, maxSum, 0
while left <= right:
mid = left + (right - left) // 2
sum = min(mid, index) * (min(mid, index) + 1) // 2 + min(mid, n - index - 1) * (min(mid, n - index) + 1) // 2
if mid > index:
sum += (mid - index - 1) * (mid - index) // 2
if mid > n - index:
sum += (mid - n + index) * (mid - n + index + 1) // 2
if sum <= maxSum:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans + 1
The problem asks to find the maximum value of nums[index] for a given array size n, position index, and maximum sum maxSum.
We have to use a binary search algorithm to maximize nums[index] in this problem. Firstly, subtract n from maxSum. This is because we want to consider the extra sum required for nums[index], as each element in nums should be at least 1. Set the initial search range as (0, maxSum). Next, we iterate until left <= right, calculating the mid-value in each iteration. For the current mid-value, we calculate its contribution to the sum on both sides of index. If the mid-value is greater than index, we add its difference to the sum. We do the same if the mid-value is greater than n-index. If the sum is within maxSum, set the answer to be the current mid-value and update the left boundary; otherwise, update the right boundary. Finally, return the answer incremented by 1 because we decreased maxSum by n earlier.
This algorithm is applied similarly in all four languages. In C++ and Java, we need to be careful with potential integer overflows and use long long (C++) or long (Java) when needed. In JavaScript, bitwise right shift (>>) is used to calculate mid-value in the binary search loop.
int maxValue(int n, int index, int maxSum) {
maxSum -= n;
int left = 0, right = maxSum, ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
long long sum = min(mid, index) * (min(mid, index) + 1LL) / 2 + min(mid, n - index - 1) * (min(mid, n - index) + 1LL) / 2;
if (mid > index) {
sum += (mid - index - 1LL) * (mid - index) / 2;
}
if (mid > n - index) {
sum += (mid - n + index) * (mid - n + index + 1) / 2;
}
if (sum <= maxSum) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans + 1;
}
The problem asks to find the maximum value of nums[index] for a given array size n, position index, and maximum sum maxSum.
We have to use a binary search algorithm to maximize nums[index] in this problem. Firstly, subtract n from maxSum. This is because we want to consider the extra sum required for nums[index], as each element in nums should be at least 1. Set the initial search range as (0, maxSum). Next, we iterate until left <= right, calculating the mid-value in each iteration. For the current mid-value, we calculate its contribution to the sum on both sides of index. If the mid-value is greater than index, we add its difference to the sum. We do the same if the mid-value is greater than n-index. If the sum is within maxSum, set the answer to be the current mid-value and update the left boundary; otherwise, update the right boundary. Finally, return the answer incremented by 1 because we decreased maxSum by n earlier.
This algorithm is applied similarly in all four languages. In C++ and Java, we need to be careful with potential integer overflows and use long long (C++) or long (Java) when needed. In JavaScript, bitwise right shift (>>) is used to calculate mid-value in the binary search loop.