🔗 Number of Divisors and Sum

Two integers left and right are given as parameters. Among all numbers from left to right, complete the solution function so that it adds up the numbers with an even number of divisors and subtracts the numbers with an odd number of divisors, then returns the result.

• 1 ≤ left ≤ right ≤ 1,000

Input/Output Example #1

The following table shows all the divisors of the numbers from 13 to 17.

So it must return 13 + 14 + 15 - 16 + 17 = 43.

Input/Output Example #2

The following table shows all the divisors of the numbers from 24 to 27.

So it must return 24 - 25 + 26 + 27 = 52.

This is a low-difficulty, simple problem. Just implementing an algorithm to find divisors is enough to solve it without much difficulty.

1. Find the divisors.
   • We don't need to know the divisors themselves, just the count is enough.
2. Check whether the divisor count is even or odd.
   1. Add it if even.
   2. Subtract it if odd.
3. Return the accumulated value.

JAVA
private int[] measure(int num)
{
	ArrayList<Integer> list = new ArrayList<>();
	
	for (int i = 1; i <= Math.sqrt(num); i++)
	{
		// If it divides evenly with the given number
		if (num % i == 0)
		{
			list.add(i);
			
			// If it's not num's square root value
			if (i * i != num)
			{
				list.add(num / i);
			}
		}
	}
	
	return list.stream().sorted().mapToInt(Integer::intValue).toArray();
}

The algorithm for finding divisors is as shown above. When finding divisors, it's enough to check up to the square root of the target number.

For example, 16 has divisors [ 1, 2, 4, 8, 16 ]. Since $\sqrt{16} = 4$, checking only up to 4 to get [ 1, 2, 4 ] is enough to know all the divisors.

This is because 16 can be inferred from 16 / 1, and 8 from 16 / 2. When i * i != num, num has its own square root as a divisor, so unlike other numbers, only i is added without also dividing num. In the example above, 4 is that case.

After that, check the divisor count and add or subtract the value depending on whether it's even or odd.

JAVA
import java.util.ArrayList;

/**
 * Number of Divisors and Sum class
 *
 * @author RWB
 * @since 2021.12.12 Sun 00:33:56
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param left: [int] integer 1
	 * @param right: [int] integer 2
	 *
	 * @return [int] the answer
	 */
	public int solution(int left, int right)
	{
		int answer = 0;
		
		for (int i = left; i <= right; i++)
		{
			int count = measure(i).length;
			
			answer += count % 2 == 0 ? i : -i;
		}
		
		return answer;
	}
	
	/**
	 * Method that returns divisors
	 *
	 * @param num: [int] number
	 *
	 * @return [int[]] divisors
	 */
	private int[] measure(int num)
	{
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int i = 1; i <= Math.sqrt(num); i++)
		{
			// If it divides evenly with the given number
			if (num % i == 0)
			{
				list.add(i);
				
				// If it's not num's square root value
				if (i * i != num)
				{
					list.add(num / i);
				}
			}
		}
		
		return list.stream().sorted().mapToInt(Integer::intValue).toArray();
	}
}