Find the Array Concatenation Value

Difficulty: Easy | Acceptance: 72.00% | Paid: No Topics: Array, Two Pointers, Simulation

You are given a 0-indexed integer array nums.

The concatenation of two numbers is the number formed by concatenating their numerals.

For example, the concatenation of 15, 49 is 1549. The concatenation value of nums is initially 0. Perform this operation until nums is empty:

If there exists more than one number in nums, pick the first element and the last element in nums and add the value of their concatenation to the concatenation value of nums, then delete the two elements. If only one element exists, add its value to the concatenation value of nums, then delete it. Return the concatenation value of the nums.

• Examples
• Constraints
• Two Pointers Simulation
• Mathematical Concatenation

Examples

Input: nums = [7,52,2,4]
Output: 596
Explanation:
- Concatenation of nums[0] and nums[3] is 74, ans = 74.
- Concatenation of nums[1] and nums[2] is 522, ans = 74 + 522 = 596.
- nums is empty, return 596.

Input: nums = [5,14,13,8,12]
Output: 673
Explanation:
- Concatenation of nums[0] and nums[4] is 512, ans = 512.
- Concatenation of nums[1] and nums[3] is 148, ans = 512 + 148 = 660.
- Only nums[2] left, ans = 660 + 13 = 673.
- nums is empty, return 673.

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 10^4

Two Pointers Simulation

Intuition We can simulate the process directly using two pointers, one at the start and one at the end of the array. We concatenate the numbers at these pointers, add the result to our answer, and move the pointers inward until they meet.

Steps

• Initialize left = 0, right = nums.length - 1, and ans = 0.
• Loop while left <= right.
• If left == right, add nums[left] to ans.
• Otherwise, convert nums[left] and nums[right] to strings, concatenate them, convert back to an integer, and add to ans.
• Increment left and decrement right.
• Return ans.

class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        ans = 0
        while l <= r:
            if l == r:
                ans += nums[l]
            else:
                ans += int(str(nums[l]) + str(nums[r]))
            l += 1
            r -= 1
        return ans

Complexity

• Time: O(N * K), where N is the length of the array and K is the maximum number of digits in an element.
• Space: O(K) for the string representation during concatenation.
• Notes: Simple and readable, but involves string conversion overhead.

Mathematical Concatenation

Intuition Instead of converting numbers to strings, we can calculate the concatenated value mathematically. To concatenate a and b, we can multiply a by 10 raised to the power of the number of digits in b, then add b.

Steps

• Initialize left = 0, right = nums.length - 1, and ans = 0.
• Loop while left <= right.
• If left == right, add nums[left] to ans.
• Otherwise, count the number of digits d in nums[right].
• Calculate the concatenated value as nums[left] * 10^d + nums[right] and add to ans.
• Increment left and decrement right.
• Return ans.

class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        ans = 0
        while l <= r:
            if l == r:
                ans += nums[l]
            else:
                # Calculate digits of nums[r]
                temp = nums[r]
                digits = 0
                while temp > 0:
                    digits += 1
                    temp //= 10
                # Concatenate
                ans += nums[l] * (10 ** digits) + nums[r]
            l += 1
            r -= 1
        return ans

Complexity

• Time: O(N * K), where N is the length of the array and K is the maximum number of digits.
• Space: O(1), as we only use a few variables for calculation.
• Notes: More efficient in terms of space as it avoids creating string objects.