Given a range [l, r], the task is to find the sum of all the even factors of the numbers from the given range.
Examples:
Input: l = 6, r = 8
Output: 22
factors(6) = 1, 2, 3, 6, evenfactors(6) = 2, 6 sumEvenFactors(6) = 2 + 6 = 8
factors(7) = 1, 7, No even factors
factors(8) = 1, 2, 4, 8, evenfactors(8) = 2, 4, 8 sumEvenFactors(8) = 2 + 4 + 8 = 14
Therefore sum of all even factors = 8 + 14 = 22
Input: l = 1, r = 10
Output: 42
Approach: We can modify Sieve Of Eratosthenes to store the sum of all even factors of a number at it’s corresponding index. Then we will make a prefix array to store sum upto that index. And now each query can be answered in O(1) using prefix[r] – prefix[l – 1].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long intconst int MAX = 100000;ll prefix[MAX];// Function to calculate the prefix sum// of all the even factorsvoid sieve_modified(){ for (int i = 2; i < MAX; i += 2) { // Add i to all the multiples of i for (int j = i; j < MAX; j += i) prefix[j] += i; } // Update the prefix sum for (int i = 1; i < MAX; i++) prefix[i] += prefix[i - 1];}// Function to return the sum of// all the even factors of the// numbers in the given rangell sumEvenFactors(int L, int R){ return (prefix[R] - prefix[L - 1]);}// Driver codeint main(){ sieve_modified(); int l = 6, r = 10; cout << sumEvenFactors(l, r); return 0;} |
Java
// Java implementation of the approachclass GFG { static final int MAX = 100000; static long prefix[] = new long[MAX]; // Function to calculate the prefix sum // of all the even factors static void sieve_modified() { for (int i = 2; i < MAX; i += 2) { // Add i to all the multiples of i for (int j = i; j < MAX; j += i) prefix[j] += i; } // Update the prefix sum for (int i = 1; i < MAX; i++) prefix[i] += prefix[i - 1]; } // Function to return the sum of // all the even factors of the // numbers in the given range static long sumEvenFactors(int L, int R) { return (prefix[R] - prefix[L - 1]); } // Driver code public static void main(String args[]) { sieve_modified(); int l = 6, r = 10; System.out.print(sumEvenFactors(l, r)); }} |
Python3
# Python3 implementation of the approach. # Function to calculate the prefix sum # of all the even factors def sieve_modified(): for i in range(2, MAX, 2): # Add i to all the multiples of i for j in range(i, MAX, i): prefix[j] += i # Update the prefix sum for i in range(1, MAX): prefix[i] += prefix[i - 1] # Function to return the sum of # all the even factors of the # numbers in the given range def sumEvenFactors(L, R): return (prefix[R] - prefix[L - 1]) # Driver code if __name__ == "__main__": MAX = 100000 prefix = [0] * MAX sieve_modified() l, r = 6, 10 print(sumEvenFactors(l, r)) # This code is contributed by Rituraj Jain |
C#
using System;// C# implementation of the approachusing System;class GFG{ public const int MAX = 100000; public static long[] prefix = new long[MAX]; // Function to calculate the prefix sum // of all the even factors public static void sieve_modified() { for (int i = 2; i < MAX; i += 2) { // Add i to all the multiples of i for (int j = i; j < MAX; j += i) { prefix[j] += i; } } // Update the prefix sum for (int i = 1; i < MAX; i++) { prefix[i] += prefix[i - 1]; } } // Function to return the sum of // all the even factors of the // numbers in the given range public static long sumEvenFactors(int L, int R) { return (prefix[R] - prefix[L - 1]); } // Driver code public static void Main(string[] args) { sieve_modified(); int l = 6, r = 10; Console.Write(sumEvenFactors(l, r)); }}// This code is contributed by Shrikant13 |
Javascript
<script>// Javascript implementation of the approachvar MAX = 100000;prefix = Array(MAX).fill(0);// Function to calculate the prefix sum// of all the even factorsfunction sieve_modified(){ for (var i = 2; i < MAX; i += 2) { // Add i to all the multiples of i for (var j = i; j < MAX; j += i) prefix[j] += i; } // Update the prefix sum for (var i = 1; i < MAX; i++) prefix[i] += prefix[i - 1];}// Function to return the sum of// all the even factors of the// numbers in the given rangefunction sumEvenFactors(L, R){ return (prefix[R] - prefix[L - 1]);}// Driver codesieve_modified();var l = 6, r = 10;document.write(sumEvenFactors(l, r));// This code is contributed by noob2000.</script> |
PHP
<?php// PHP implementation of the approach$MAX = 10000;$prefix = array_fill(0, $MAX, 0);// Function to calculate the prefix sum// of all the even factorsfunction sieve_modified(){ global $MAX, $prefix; for ($i = 2; $i < $MAX; $i += 2) { // Add i to all the multiples of i for ($j = $i; $j < $MAX; $j += $i) $prefix[$j] += $i; } // Update the prefix sum for ($i = 1; $i < $MAX; $i++) $prefix[$i] += $prefix[$i - 1];}// Function to return the sum of// all the even factors of the// numbers in the given rangefunction sumEvenFactors($L, $R){ global $MAX, $prefix; return ($prefix[$R] - $prefix[$L - 1]);}// Driver codesieve_modified();$l = 6;$r = 10;echo sumEvenFactors($l, $r);// This code is contributed by mits?> |
34
Approach#2: Using math
Define a function that takes two inputs l and r, the range of numbers Create an empty list to store the even factors of each number Iterate through the range of numbers from l to r (inclusive) For each number, find its factors by iterating from 1 to the square root of the number (inclusive) For each factor, check if it is even If the factor is even, append it to the list of even factors After iterating through all factors, sum up the even factors and return the total sum as output
Algorithm
1. Define a function, sum_even_factors, that takes two integer inputs, l and r
2. Create an empty list, even_factors
3. For i in range l to r (inclusive)
a. Create an empty list, factors
b. For j in range 1 to square root of i+1 (inclusive)
i. If i % j == 0, append j to the list factors, and if i//j is not equal to j, append i//j to the list factors
c. For factor in factors:
i. If factor % 2 == 0, append factor to the list even_factors
4. Return the sum of the elements in the list even_factors as output
C++
#include <iostream>#include <cmath>#include <vector>int sumEvenFactors(int l, int r) { std::vector<int> evenFactors; for (int i = l; i <= r; ++i) { std::vector<int> factors; for (int j = 1; j <= std::sqrt(i); ++j) { if (i % j == 0) { factors.push_back(j); if (i / j != j) { factors.push_back(i / j); } } } for (int factor : factors) { if (factor % 2 == 0) { evenFactors.push_back(factor); } } } int sum = 0; for (int factor : evenFactors) { sum += factor; } return sum;}int main() { int l = 6; int r = 10; std::cout << sumEvenFactors(l, r) << std::endl; return 0;}// This code is contributed by Dwaipayan Bandyopadhyay |
Python3
import mathdef sum_even_factors(l, r): even_factors = [] for i in range(l, r+1): factors = [] for j in range(1, int(math.sqrt(i))+1): if i % j == 0: factors.append(j) if i//j != j: factors.append(i//j) for factor in factors: if factor % 2 == 0: even_factors.append(factor) return sum(even_factors)l, r = 6, 10print(sum_even_factors(l, r)) |
Javascript
// Javascript code addition function sumEvenFactors(l, r) { let evenFactors = []; for (let i = l; i <= r; i++) { let factors = []; for (let j = 1; j <= Math.sqrt(i); j++) { if (i % j == 0) { factors.push(j); if (i / j != j) { factors.push(i / j); } } } for (let factor of factors) { if (factor % 2 == 0) { evenFactors.push(factor); } } } return evenFactors.reduce((acc, val) => acc + val, 0);}let l = 6;let r = 10;console.log(sumEvenFactors(l, r));// The code is contributed by Arushi goel. |
34
Time complexity: O(n * sqrt(n)),where n represents the range of numbers between l and r
Space complexity: O(n), where n represents the range of numbers between l and r
METHOD 3:Using counter method.
APPROACH:
The program finds the sum of all even factors of numbers in a given range using a list comprehension to generate the even factors and a Counter object to count their occurrences. The sum is computed by iterating over the factor-count pairs in the Counter object and multiplying the factor by its count.
ALGORITHM:
1.Initialize an empty list to store the even factors of numbers in the range [l, r].
2.Iterate over each number in the range [l, r].
3.For each number, iterate over each factor in the range [2, num+1].
4.Check if the factor divides the number evenly and if it is even.
5.If both conditions are satisfied, add the factor to the list of even factors.
6.Create a Counter object from the list of even factors to count the number of occurrences of each factor.
7.Iterate over each factor-count pair in the Counter object and multiply the factor by its count.
8.Add up the products computed in step 7 to obtain the total sum of all even factors.
Python3
from collections import Counterdef sum_even_factors_counter(l, r): factors = [factor for num in range(l, r+1) for factor in range(2, num+1) if num % factor == 0 and factor % 2 == 0] factor_counts = Counter(factors) total_sum = sum([factor * count for factor, count in factor_counts.items()]) return total_suml, r = 6, 10result = sum_even_factors_counter(l, r)print(result) # Output: 34 |
34
Time complexity:
The time complexity of this algorithm is O((r-l+1) * sqrt(r)), where r-l+1 is the size of the input range [l, r], and sqrt(r) is the maximum number of factors that any number in the range [l, r] can have. The inner loop that checks for factors runs from 2 to num+1, which takes O(sqrt(r)) time on average. The outer loop runs r-l+1 times.
Space complexity:
The space complexity of this algorithm is O(sqrt(r)) to store the list of even factors, plus the space required by the Counter object to store the counts of each factor.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
