We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Array Concatenation Value

Number: 2698

Difficulty: Easy

Paid? No

Companies: IBM

Problem Description

Given a 0-indexed integer array nums, repeatedly perform the following operations until nums becomes empty: if the array contains more than one element, remove the first and last elements, concatenate them (by placing the first element's digits in front of the last element's digits), and add the result to a running total; if only one element remains, add its value to the total and remove it. Return the final total, known as the concatenation value.

Key Insights

  • Use two pointers (one at the beginning and one at the end) to simulate the removal process.
  • Concatenating two numbers can be achieved by multiplying the first number by 10^(number of digits of the second number) and then adding the second number.
  • The process runs in linear time relative to the length of the array.
  • Handle the edge case where there is one element left.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We utilize a two pointers approach, with one pointer starting at the beginning of the array and the other at the end. During each iteration, if both pointers refer to different elements, we compute the concatenated number by determining the number of digits in the second element and then adding first * (10^digits) + last to the result. The pointers are then moved inward. If the pointers meet (indicating a single remaining element), we add that element to the result and terminate. This method ensures that each element is processed once, making the solution efficient.

Code Solutions

# Python solution using two pointers

def findTheArrayConcVal(nums):
    # Initialize pointers and the result variable
    left, right = 0, len(nums) - 1
    total = 0
    
    # Helper function to get the number of digits in a number
    def count_digits(num):
        # Count digits by converting to string (alternative: logarithmic approach)
        return len(str(num))
    
    # Process the array until pointers cross
    while left <= right:
        if left == right:  # Only one element remains
            total += nums[left]
        else:
            # Calculate the power based on number of digits in the right element
            digits = count_digits(nums[right])
            # Compute concatenation by shifting left element and adding right element
            total += nums[left] * (10 ** digits) + nums[right]
        left += 1
        right -= 1
    
    return total

# Example usage:
print(findTheArrayConcVal([7, 52, 2, 4]))  # Expected output: 596
← Back to All Questions