Special Sum of Array
You have been given an array/list ‘arr’ of length ‘N’, which contains single digit elements at every index. Your task is to return the sum of all elements of the array. But the final sum should also be a single digit.

To keep the output single digit - you need to keep adding the digits of the output number till a single digit is left.

For example:

For the given array [5, 8, 4, 9] The sum of the elements of the array will be 5 + 8 + 4 + 9 = 26. Since 26 is not a single-digit number, we will again take the sum of the digits of 26. 2 + 6 = 8. Now 8 is a single-digit number. So we will stop here and return 8.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow. The first line of each test case contains a single integer ‘N’, representing the size of the array. The second line of each test case contains ‘N’ space-separated integers representing the elements of the given array.

Output Format:

For each test case, print a single-digit integer representing the sum of the array. Output for each test case will be printed in a separate line.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Special Sum of Array

You have been given an array/list ‘arr’ of length ‘N’, which contains single digit elements at every index. Your task is to return the sum of all elements of the array. But the final sum should also be a single digit.

To keep the output single digit - you need to keep adding the digits of the output number till a single digit is left.

For example:

For the given array [5, 8, 4, 9]

The sum of the elements of the array will be
5 + 8 + 4 + 9 = 26.
Since 26 is not a single-digit number, we will again take the sum of the digits of 26. 
2 + 6 = 8.
Now 8 is a single-digit number. So we will stop here and return 8.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the size of the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the given array.

Output Format:

For each test case, print a single-digit integer representing the sum of the array.

Output for each test case will be printed in a separate line.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 10^3
0 <= arr[i] <= 9

It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 10^5.

Time Limit: 1 sec.

Accepted Answer

The brute force problem will lead to overflow and hence all test cases will not pass.
So, we had to give the most optimized solution

Accepted Answer

Brute Force

We will iterate from left to right and will calculate the sum of the elements and if the sum becomes a double-digit number we will make it a single-digit number according to the steps given in the problem statement.

Algorithm:

Create a variable ‘SUM’ of type integer and initialize it with zero.
Start iterating the array from left to right and add the current element to the sum.
If ‘SUM’ is greater than 9, create another variable ‘TempSum’, and store the sum of digits of the variable ‘SUM’ in it.
Then update ‘SUM’ as ‘TempSum’.
Finally, output the ‘SUM’.

Space Complexity: O(1)Explanation:

O( 1 ).

Constant extra space is used.

Time Complexity: O(n)Explanation:

O( N ), where ‘N’ is the number of elements in the array.

We will iterate over the array and will visit every element only once. So, the time complexity is O( N ).

Python (3.5)

'''
    Time Complexity: O( N ).
    Space Complexity: O( 1 ).
    
    Where, N is the size of the array/list.
'''

def specialSum(arr, n):
    
    # Declare a variable 'sum' and initialize it with zero.
    summ = 0
    
    for i in range(n):
        
        # Add each element to the variable 'sum'.
        summ += arr[i]
        
        if summ > 9:
            
            '''
                Store the sum of the digits of the variable
                'sum' in a new variable 'tempSum'.
            '''
            tempSum = 0
            tempSum += summ % 10
            summ = summ // 10
            tempSum += summ
            
            # Update 'sum' as 'tempSum'.
            summ = tempSum
            
    return summ

C++ (g++ 5.4)

/*
    Time Complexity: O( N ).
    Space Complexity: O( 1 ).
    
    Where, N is the size of the array/list.
*/

int specialSum(vector& arr, int n){

    // Declare a variable 'sum' and initialize it with zero.
    int sum = 0;

    for(int i = 0; i < n; i ++){

        // Add each element to the variable 'sum'.
        sum += arr[i];

        if( sum > 9 ){

            /*
                Store the sum of the digits of the variable 
               'sum' in a new variable 'tempSum'.
            */
            int tempSum = 0;
            tempSum += sum % 10;
            sum /= 10;
            tempSum += sum;

            // Update 'sum' as 'tempSum'. 
            sum = tempSum;
        }
    }

    return sum;

}

Java (SE 1.8)

/*

    Time Complexity: O(N).

    Space Complexity: O(1).

    

    Where, N is the size of the array/list.

*/



import java.util.ArrayList;



public class Solution {

    public static int specialSum(ArrayList arr, int n) {



        // Declare a variable 'sum' and initialize it with zero.

        int sum = 0;

        

        for (int i = 0; i < n; i++) {



            // Add each element to the variable 'sum'.

            sum += arr.get(i);



            if (sum > 9) {



                /*

                    Store the sum of the digits of the variable

                    'sum' in a new variable 'tempSum'.

                */

                int tempSum = 0;

                tempSum += sum % 10;

                sum /= 10;

                tempSum += sum;



                // Update 'sum' as 'tempSum'.

                sum = tempSum;

            }

        }



        return sum;



    }

}