Java Coding Test Course, Finding the Sum of Remainders

Hello! In today’s lecture, we will solve an algorithm problem called “Sum of Remainders” using Java. This problem involves finding the remainders when a given integer array is divided by a specified number and then summing those remainders. This problem covers important basic concepts for preparing for coding tests.

Problem Description

Given an integer array arr and an integer m, write a function that calculates the remainder of each element in the array when divided by m and returns the total sum of those remainders.

Input

  • The first line contains the size of the array n (1 ≤ n ≤ 100,000).
  • The second line contains n integers arr[i] (1 ≤ arr[i] ≤ 1,000,000) separated by spaces.
  • The third line contains the integer m (1 ≤ m ≤ 1,000,000).

Output

Print the sum of the remainders after dividing the elements of the array by m.

Example

Input:
5
1 2 3 4 5
3

Output:
15

Problem-Solving Strategy

To solve this problem, follow these steps:

  1. After receiving the integer array and integer m, calculate the remainders for all elements in the array using m.
  2. Add all those remainder values together.
  3. Print the final result.

Implementation

Now, let’s implement the above strategy in Java. First, we will write a method to input the array and calculate the remainder for each element when divided by m. Below is the Java code that solves this problem:


import java.util.Scanner;

public class RemainderSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 1. Input
        int n = scanner.nextInt(); // size of the array
        int[] arr = new int[n];
        
        // Input array elements
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        int m = scanner.nextInt(); // divisor

        // 2. Calculate sum of remainders
        long remainderSum = 0; // variable to store the result
        for (int i = 0; i < n; i++) {
            remainderSum += arr[i] % m; // add remainders
        }

        // 3. Print result
        System.out.println(remainderSum);
        
        scanner.close();
    }
}

Code Explanation

  1. Input Handling: The Scanner class is used to handle input. First, it reads the size of the array n, then stores each element in arr. Finally, it reads the integer m that we want to divide by.
  2. Calculating the Sum of Remainders: After initializing the remainderSum variable, a loop is used to add the remainders of each element in the array divided by m. The long type is used to safely store the sum of large numbers.
  3. Output Result: Finally, the sum of the remainders is printed.

Complexity Analysis

The time complexity of this programming problem is O(n). Due to the length of the array, we need to iterate through all elements in the worst case. The space complexity is O(1) as there is almost no additional space required.

Additional Example Tests

It is also good to consider a few additional test cases after implementing:

Example 1

Input:
3
5 10 15
4

Output:
6

Example 2

Input:
4
1 100 10000 1000000
1

Output:
0

Example 3

Input:
5
0 10 20 30 40
7

Output:
10

Conclusion

Today, we solved the "Sum of Remainders" problem using Java. Through this example, we learned how to effectively utilize array processing, loops, and remainder calculations. These types of problems can be transformed in various ways, helping to build adaptability. We hope to improve our skills by solving many different algorithm problems in the future!

Thank you!