Given three integers L, R, and K, the task is to find the maximum sum of K even multiples of 5 from the range [L, R].
Examples:
Input: L = 7, R = 48, K = 3
Output: 90
Explanation: Maximum sum of 3 even multiples of 5 in the range [7, 48] = 40 + 30 + 20 = 90Input: L = 16, R= 60, K = 4
Output: 180
Explanation: Maximum sum of 4 even multiples of 5 in the range [16, 60] = 60 + 50 + 40 + 30 = 180
Naive Approach: The simplest approach is to iterate over all even elements from R to L, and for every element, check if it is divisible by 5 or not. If found to be true, add that element to the sum and decrement K. When K reaches 0, break the loop and print the obtained sum.
Time Complexity: O(N), where N=R-L
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observation:
Count of even multiples of 5 in the range [1, X] = X / 10
Count of even multiples of 5 in range [L, R] = (R / 10 – L / 10) + 1 = N(say)
Maximum sum of K even multiples of 5 in range [L, R]
= Sum of even multiples of 5 in range [1, R] – Sum of even multiples of 5 in range [1, R – K]
= 10 * (N * (N + 1) / 2 – M * (M + 1) / 2), where M = R – K
Follow the steps below to solve the problem:
- Initialize N = (R / 10 – L / 10) + 1 to store the count of even multiples of 5 in the range [L, R].
- If K > N, print -1 indicating that there are less than K even multiples of 5 in the range [L, R].
- Otherwise:
- Initialize M = R – K.
- Store sum = 10 * (N * (N + 1) / 2 – M * (M + 1) / 2).
- Print sum.
Below is the implementation of the above approach:
C++14
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of K// even multiples of 5 in the range [L, R]void maxksum(int L, int R, int K){ // Store the total number of even // multiples of 5 in the range [L, R] int N = (R / 10 - L / 10) + 1; // Check if K > N if (K > N) { // If true, print -1 and return cout << -1; return; } // Otherwise, divide R by 10 R = R / 10; // Store the sum using the formula int X = R - K; int sum = 10 * ((R * (R + 1)) / 2 - (X * (X + 1)) / 2); // Print the sum cout << sum;}// Driver Codeint main(){ // Given L, R and K int L = 16, R = 60, K = 4; // Function Call maxksum(L, R, K); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*; class GFG{ // Function to find the maximum sum of K// even multiples of 5 in the range [L, R]static void maxksum(int L, int R, int K){ // Store the total number of even // multiples of 5 in the range [L, R] int N = (R / 10 - L / 10) + 1; // Check if K > N if (K > N) { // If true, print -1 and return System.out.print("-1"); return; } // Otherwise, divide R by 10 R = R / 10; // Store the sum using the formula int X = R - K; int sum = 10 * ((R * (R + 1)) / 2 - (X * (X + 1)) / 2); // Print the sum System.out.print( sum);}// Driver Codepublic static void main(String[] args) { // Given L, R and K int L = 16, R = 60, K = 4; // Function Call maxksum(L, R, K);}}// This code is contributed by Stream_Cipher |
Python3
# Python3 program to implement# the above approach# Function to find the maximum sum of K# even multiples of 5 in the range [L, R]def maxksum(L, R, K) : # Store the total number of even # multiples of 5 in the range [L, R] N = (R // 10 - L // 10) + 1; # Check if K > N if (K > N) : # If true, print -1 and return print(-1); return; # Otherwise, divide R by 10 R = R // 10; # Store the sum using the formula X = R - K; sum = 10 * ((R * (R + 1)) // 2 - (X * (X + 1)) // 2); # Print the sum print(sum);# Driver Codeif __name__ == "__main__" : # Given L, R and K L = 16; R = 60; K = 4; # Function Call maxksum(L, R, K); # This code is contributed by AnkThon |
C#
// C# program to implement// the above approach using System;class GFG{ // Function to find the maximum sum of K// even multiples of 5 in the range [L, R]static void maxksum(int L, int R, int K){ // Store the total number of even // multiples of 5 in the range [L, R] int N = (R / 10 - L / 10) + 1; // Check if K > N if (K > N) { // If true, print -1 and return Console.Write("-1"); return; } // Otherwise, divide R by 10 R = R / 10; // Store the sum using the formula int X = R - K; int sum = 10 * ((R * (R + 1)) / 2 - (X * (X + 1)) / 2); // Print the sum Console.Write( sum);} // Driver codepublic static void Main(){ // Given L, R and K int L = 16, R = 60, K = 4; // Function Call maxksum(L, R, K);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the maximum sum of K// even multiples of 5 in the range [L, R]function maxksum(L, R, K){ // Store the total number of even // multiples of 5 in the range [L, R] let N = (R / 10 - L / 10) + 1; // Check if K > N if (K > N) { // If true, print -1 and return document.write("-1"); return; } // Otherwise, divide R by 10 R = R / 10; // Store the sum using the formula let X = R - K; let sum = 10 * ((R * (R + 1)) / 2 - (X * (X + 1)) / 2); // Print the sum document.write(sum);}// Driver Code// Given L, R and Klet L = 16, R = 60, K = 4;// Function Callmaxksum(L, R, K);// This code is contributed by splevel62</script> |
180
Time Complexity: O(1)
Auxiliary Space: O(1)
