alive_ak4c's blog

By alive_ak4c, history, 5 weeks ago, In English

I came across the following question: There is a string of numbers. You need to find out the longest substring of size 2K such that the sum of K elements from left equals to sum of K elements from right.

Eg:

Input: 000000

Output: 6

Input: 123123

Output: 6

Input: 31221684

Output:4 (since 1221 is the longest substring of 31221684 that satisfies the conditions mentioned above and its length is 4)

My Solution: 1. create an array of size n. Each element of the array will contain the sum of all previous elements plus the current element. Eg: For input string: 31221684, the resultant array will be [3,4,6,8,9,15,23,27] 2. Iterate through a loop starting with largest even length possible all the way to 0 For each iteration take the length as window and slide it through the array created in step 1 For each slide calculate the sum of K elements from the left and sum of K elements from the right If they are equal then print the length and come out of all loops, if they are not equal continue looping 3. If it is unable to find the answer after all iteration print length as 0

My Code:

tc = int(input())
while tc!=0:
    current_string = input()
    n = len(current_string)
    arr = []
    curr_sum = 0
    for i in current_string:
        curr_sum += int(i)
        arr.append(curr_sum)
    if n%2 != 0:
        n = n-1
    found = False
    for curr_string_len in range(n,0,-2):
        for position in range(curr_string_len-1, n):
            mid_left = position//2
            left = position-curr_string_len
            left_sum = arr[mid_left] if left < 0 else arr[mid_left]-arr[left]
            right_sum = arr[position]-arr[mid_left]
            if left_sum == right_sum:
                print(curr_string_len)
                found = True
                break
        if found:
            break
    if not found:
        print(0)
    tc-=1

This Solution is O(n^2) time and O(n) space complexity. But this solution is not being accepted. So, can you provide me any competitive programming site with this question and it's solution (in python3) Or, suggest anything wrong with the solution? (Not GeeksForGeeks as it is the one not accepting the solution.)

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by alive_ak4c (previous revision, new revision, compare).