You are given a string of length 2N consisting of only digits from 0 to 9. You can make a move to choose an arbitrary position and replace the digit in that position with any digit from 0 to 9.
Task
Determine the minimum number moves required to make the sum of the first N digits equal to the sum of the N digits that follow.
Note: 1-based indexing is used.
Example
Assumptions
- N = 3
- S = 111279
Approach
- Change S[1] from 1 to 9
- Change S[5] from 7 to 0
Now, S = 911209
Therefore, the sum of S[1] to S[3] = 9 + 1 + 1 = 11 and the sum of S[4] to S[6] = 2 + 0 + 9 = 11.
Hence, the minimum number of moves required is 2.
Note: There can be other possible ways to achieve the answer, but we can not get the required result sum in less than 2 changes.
Function description
Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the answer:
- N: Represents an integer denoting N
- S: Represents a string denoting S
Input format
Note: This is the input format you must use to provide custom input (available above the Compile and Test button).
- The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
- For each test case:
- The first line contains an integer N.
- The next line contains a string S of length 2N.
Output format
For each test case, print the answer in a new line.
Constraints
\(1 \leq T \leq 10\)
\(1 \leq N \leq 10^5\)
Code snippets (also called starter code/boilerplate code)
This question has code snippets for C, CPP, Java, and Python.