codility-sum-of-digits.java

Solution.java

import java.util.Arrays;

/**
 * A nonempty Zero-indexed array A consisting of N integers is given.
 * This array contains a decimal representation of a number V,
 * i.e. element A[K] contains the K-th least significant digit of the decimal
 * representation of V.
 *
 * For example, array A such that:
 *     A[0] = 3
 *     A[1] = 5
 *     A[2] = 1
 * represents the number V = 153.
 *
 * Write a function:
 *     class Solution { public int solution(int[] A); }
 *
 * that, given an array A consisting of N integers specifying a decimal
 * representation of a number V, returns the sum of the digits in the
 * decimal representation of the number 17*V.
 *
 * For example, given array A such that:
 *     A[0] = 3
 *     A[1] = 5
 *     A[2] = 1
 * the function should return 9, because:
 *     - array A represents the number 153,
 *     - 17 * 153 = 2601,
 *     - the sum of the digits in the decimal representation of 2601 is
 *       2+6+0+1 = 9.
 *
 * Assume that:
 *     - N is an integer within the range [1 .. 1,000,000];
 *     - each element of array A is an integer within the range [0 .. 9],
 *
 * Complexity:
 *     - expected worst-case time complexity is O(N);
 *     - expected worst-case space complexity is O(1), beyond input storage
 *       ( not counting the storage required for input arguments).
 *
 *  Elements of input arrays can be modified.
 */
class Solution {
    private static int MULTIPLIER = 17;

    // 제출 후 재작성. 정확도 미확인
    public int solution(int[] A) {
        int digitSum = 0;  // 결과: 각 자리수의 합
        int carry = 0;
        for(int i = 0 ; i < A.length ; i++) {
            int x = A[i] * MULTIPLIER + carry;
            int digit = x % 10;
            carry = (x - digit) / 10;
            digitSum += digit;
        }
        digitSum += carry % 10 + carry / 10;
        return digitSum;
    }

    // main, test() 는 Codility에서 사용하지 않음
    public static void main(String[] args) {
        test(new int[] {3,5,1}, 9);
        test(new int[] {4,3,2,1}, 26);
        test(new int[] {5}, 13);
        test(new int[] {9}, 9);
        test(new int[] {0,1}, 8);
        test(new int[] {1,1}, 16);
        test(new int[] {9,0,9,0,9,0,9,0,9,0,9,0,9,0,9,0,9}, 81);
        test(new int[] {9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9},405);
        test(new int[] {}, 0);
    }

    private static void test(int[] A, int expected) {
        int actual = new Solution().solution(A);
        if (expected == actual) {
            System.out.print("[+] ");
        } else {
            System.out.print("[-] ");
        }
        System.out.printf("%s: expected=%d, actual=%d\n", Arrays.toString(A), expected, actual);
    }
}

정확도: 100%, 성능: 75% (제출 당시 기준. 첫 리비전 볼 것)