Suma de todos los números en el rango dado que son divisibles por M

Dados tres números A, B y M tales que A < B , la tarea es encontrar la suma de los números divisibles por M en el rango [A, B] .

Ejemplos:

Entrada: A = 25, B = 100, M = 30
Salida: 180
Explicación:
En el rango dado [25, 100] 30, 60 y 90 son los números que son divisibles por M = 30
Por lo tanto, la suma de estos números = 180 .

Entrada: A = 6, B = 15, M = 3
Salida: 42
Explicación:
En el rango dado [6, 15] 6, 9, 12 y 15 son los números que son divisibles por M = 3.
Por lo tanto, la suma de estos números = 42.

Enfoque ingenuo: verifique para cada número en el rango [A, B] si son divisibles por M o no. Y finalmente, suma todos los números que son divisibles por M.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find the sum of numbers
// divisible by M in the given range
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of numbers
// divisible by M in the given range
int sumDivisibles(int A, int B, int M)
{
    // Variable to store the sum
    int sum = 0;
 
    // Running a loop from A to B and check
    // if a number is divisible by i.
    for (int i = A; i <= B; i++)
 
        // If the number is divisible,
        // then add it to sum
        if (i % M == 0)
            sum += i;
 
    // Return the sum
    return sum;
}
 
// Driver code
int main()
{
    // A and B define the range
    // M is the dividend
    int A = 6, B = 15, M = 3;
 
    // Printing the result
    cout << sumDivisibles(A, B, M) << endl;
 
    return 0;
}

Java

// Java program to find the sum of numbers
// divisible by M in the given range
import java.util.*;
 
class GFG{
  
// Function to find the sum of numbers
// divisible by M in the given range
static int sumDivisibles(int A, int B, int M)
{
    // Variable to store the sum
    int sum = 0;
  
    // Running a loop from A to B and check
    // if a number is divisible by i.
    for (int i = A; i <= B; i++)
  
        // If the number is divisible,
        // then add it to sum
        if (i % M == 0)
            sum += i;
  
    // Return the sum
    return sum;
}
  
// Driver code
public static void main(String[] args)
{
    // A and B define the range
    // M is the dividend
    int A = 6, B = 15, M = 3;
  
    // Printing the result
    System.out.print(sumDivisibles(A, B, M) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 program to find the sum of numbers
# divisible by M in the given range
 
# Function to find the sum of numbers
# divisible by M in the given range
def sumDivisibles(A, B, M):
 
    # Variable to store the sum
    sum = 0
 
    # Running a loop from A to B and check
    # if a number is divisible by i.
    for i in range(A, B + 1):
 
        # If the number is divisible,
        # then add it to sum
        if (i % M == 0):
            sum += i
 
    # Return the sum
    return sum
 
# Driver code
if __name__=="__main__":
     
    # A and B define the range
    # M is the dividend
    A = 6
    B = 15
    M = 3
 
    # Printing the result
    print(sumDivisibles(A, B, M))
     
# This code is contributed by chitranayal

C#

// C# program to find the sum of numbers
// divisible by M in the given range
using System;
 
class GFG{
   
// Function to find the sum of numbers
// divisible by M in the given range
static int sumDivisibles(int A, int B, int M)
{
    // Variable to store the sum
    int sum = 0;
   
    // Running a loop from A to B and check
    // if a number is divisible by i.
    for (int i = A; i <= B; i++)
   
        // If the number is divisible,
        // then add it to sum
        if (i % M == 0)
            sum += i;
   
    // Return the sum
    return sum;
}
   
// Driver code
public static void Main(String[] args)
{
    // A and B define the range
    // M is the dividend
    int A = 6, B = 15, M = 3;
   
    // Printing the result
    Console.Write(sumDivisibles(A, B, M) +"\n");
}
}
  
// This code is contributed by sapnasingh4991

Javascript

<script>
 
// Javascript program to find the sum of numbers
// divisible by M in the given range
 
// Function to find the sum of numbers
// divisible by M in the given range
function sumDivisibles(A, B, M)
{
     
    // Variable to store the sum
    var sum = 0;
 
    // Running a loop from A to B and check
    // if a number is divisible by i.
    for(var i = A; i <= B; i++)
     
        // If the number is divisible,
        // then add it to sum
        if (i % M == 0)
            sum += i;
 
    // Return the sum
    return sum;
}
 
// Driver code
 
// A and B define the range
// M is the dividend
var A = 6, B = 15, M = 3;
 
// Printing the result
document.write(sumDivisibles(A, B, M));
 
// This code is contributed by rrrtnx
 
</script>

Producción:

Complejidad temporal: O(N).
Enfoque Eficiente: La idea es utilizar el concepto de Progresión Aritmética y divisibilidad.

Tras la visualización, se puede ver que los múltiplos de M forman una serie

M, 2M, 3M, ...

Si podemos encontrar el valor de K que es el primer término en el rango [A, B] que es divisible por M, entonces directamente, la serie sería:

K, (K + M), (K + 2M), ------  (K + (N - 1)*M )
where N is the number of elements in the series.

Por lo tanto, el primer término ‘K’ de la serie no es más que el mayor número menor o igual que A que es divisible por M.
De manera similar, el último término es el número más pequeño mayor o igual que B que es divisible por M.
Sin embargo, si alguno de los números anteriores excede el rango, entonces podemos restarle M directamente para llevarlo al rango.
Y, el número de términos divisibles por M se puede encontrar mediante la fórmula:

N = B / M - (A - 1)/ M

Por lo tanto, la suma de los elementos se puede encontrar por:

sum = N * ( (first term + last term) / 2)

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find the sum of numbers
// divisible by M in the given range
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest number
// smaller than or equal to N
// that is divisible by K
int findSmallNum(int N, int K)
{
    // Finding the remainder when N is
    // divided by K
    int rem = N % K;
 
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
 
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N - rem;
}
 
// Function to find the smallest number
// greater than or equal to N
// that is divisible by K
int findLargeNum(int N, int K)
{
    // Finding the remainder when N is
    // divided by K
    int rem = (N + K) % K;
 
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
 
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N + K - rem;
}
 
// Function to find the sum of numbers
// divisible by M in the given range
int sumDivisibles(int A, int B, int M)
{
    // Variable to store the sum
    int sum = 0;
    int first = findSmallNum(A, M);
    int last = findLargeNum(B, M);
 
    // To bring the smallest and largest
    // numbers in the range [A, B]
    if (first < A)
        first += M;
 
    if (last > B)
        first -= M;
 
    // To count the number of terms in the AP
    int n = (B / M) - (A - 1) / M;
 
    // Sum of n terms of an AP
    return n * (first + last) / 2;
}
 
// Driver code
int main()
{
    // A and B define the range,
    // M is the dividend
    int A = 6, B = 15, M = 3;
 
    // Printing the result
    cout << sumDivisibles(A, B, M);
 
    return 0;
}

Java

// Java program to find the sum of numbers
// divisible by M in the given range
 
 
class GFG{
  
// Function to find the largest number
// smaller than or equal to N
// that is divisible by K
static int findSmallNum(int N, int K)
{
    // Finding the remainder when N is
    // divided by K
    int rem = N % K;
  
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
  
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N - rem;
}
  
// Function to find the smallest number
// greater than or equal to N
// that is divisible by K
static int findLargeNum(int N, int K)
{
    // Finding the remainder when N is
    // divided by K
    int rem = (N + K) % K;
  
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
  
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N + K - rem;
}
  
// Function to find the sum of numbers
// divisible by M in the given range
static int sumDivisibles(int A, int B, int M)
{
    // Variable to store the sum
    int first = findSmallNum(A, M);
    int last = findLargeNum(B, M);
  
    // To bring the smallest and largest
    // numbers in the range [A, B]
    if (first < A)
        first += M;
  
    if (last > B)
        first -= M;
  
    // To count the number of terms in the AP
    int n = (B / M) - (A - 1) / M;
  
    // Sum of n terms of an AP
    return n * (first + last) / 2;
}
  
// Driver code
public static void main(String[] args)
{
    // A and B define the range,
    // M is the dividend
    int A = 6, B = 15, M = 3;
  
    // Printing the result
    System.out.print(sumDivisibles(A, B, M));
  
}
}
 
// This code contributed by Princi Singh

Python3

# Python3 program to find the sum of numbers
# divisible by M in the given range
 
# Function to find the largest number
# smaller than or equal to N
# that is divisible by K
def findSmallNum(N, K):
     
    # Finding the remainder when N is
    # divided by K
    rem = N % K
 
    # If the remainder is 0, then the
    # number itself is divisible by K
    if (rem == 0):
        return N
    else:
        # Else, then the difference between
        # N and remainder is the largest number
        # which is divisible by K
        return N - rem
 
# Function to find the smallest number
# greater than or equal to N
# that is divisible by K
def findLargeNum(N, K):
     
    # Finding the remainder when N is
    # divided by K
    rem = (N + K) % K
 
    # If the remainder is 0, then the
    # number itself is divisible by K
    if (rem == 0):
        return N
    else:
        # Else, then the difference between
        # N and remainder is the largest number
        # which is divisible by K
        return N + K - rem
 
# Function to find the sum of numbers
# divisible by M in the given range
def sumDivisibles(A, B, M):
     
    # Variable to store the sum
    sum = 0
    first = findSmallNum(A, M)
    last = findLargeNum(B, M)
 
    # To bring the smallest and largest
    # numbers in the range [A, B]
    if (first < A):
        first += M
 
    if (last > B):
        first -= M
 
    # To count the number of terms in the AP
    n = (B // M) - (A - 1) // M
 
    # Sum of n terms of an AP
    return n * (first + last) // 2
 
# Driver code
if __name__ == '__main__':
     
    # A and B define the range,
    # M is the dividend
    A = 6
    B = 15
    M = 3
 
    # Printing the result
    print(sumDivisibles(A, B, M))
 
# This code is contributed by Surendra_Gangwar

C#

// C# program to find the sum of numbers
// divisible by M in the given range
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to find the largest number
// smaller than or equal to N
// that is divisible by K
static int findSmallNum(int N, int K)
{
    // Finding the remainder when N is
    // divided by K
    int rem = N % K;
   
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
   
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N - rem;
}
   
// Function to find the smallest number
// greater than or equal to N
// that is divisible by K
static int findLargeNum(int N, int K)
{
    // Finding the remainder when N is
    // divided by K
    int rem = (N + K) % K;
   
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
   
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N + K - rem;
}
   
// Function to find the sum of numbers
// divisible by M in the given range
static int sumDivisibles(int A, int B, int M)
{
    // Variable to store the sum
    int first = findSmallNum(A, M);
    int last = findLargeNum(B, M);
   
    // To bring the smallest and largest
    // numbers in the range [A, B]
    if (first < A)
        first += M;
   
    if (last > B)
        first -= M;
   
    // To count the number of terms in the AP
    int n = (B / M) - (A - 1) / M;
   
    // Sum of n terms of an AP
    return n * (first + last) / 2;
}
   
// Driver code
public static void Main(String[] args)
{
    // A and B define the range,
    // M is the dividend
    int A = 6, B = 15, M = 3;
   
    // Printing the result
    Console.Write(sumDivisibles(A, B, M));
   
}
}
  
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program to find the sum of numbers
// divisible by M in the given range
 
// Function to find the largest number
// smaller than or equal to N
// that is divisible by K
function findSmallNum(N, K)
{
     
    // Finding the remainder when N is
    // divided by K
    var rem = N % K;
 
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
 
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N - rem;
}
 
// Function to find the smallest number
// greater than or equal to N
// that is divisible by K
function findLargeNum(N, K)
{
     
    // Finding the remainder when N is
    // divided by K
    var rem = (N + K) % K;
 
    // If the remainder is 0, then the
    // number itself is divisible by K
    if (rem == 0)
        return N;
    else
 
        // Else, then the difference between
        // N and remainder is the largest number
        // which is divisible by K
        return N + K - rem;
}
 
// Function to find the sum of numbers
// divisible by M in the given range
function sumDivisibles(A, B, M)
{
     
    // Variable to store the sum
    var sum = 0;
    var first = findSmallNum(A, M);
    var last = findLargeNum(B, M);
 
    // To bring the smallest and largest
    // numbers in the range [A, B]
    if (first < A)
        first += M;
 
    if (last > B)
        first -= M;
 
    // To count the number of terms in the AP
    var n = (parseInt(B / M) -
             parseInt((A - 1) / M));
 
    // Sum of n terms of an AP
    return n * (first + last) / 2;
}
 
// Driver code
 
// A and B define the range,
// M is the dividend
var A = 6, B = 15, M = 3;
 
// Printing the result
document.write( sumDivisibles(A, B, M));
 
// This code is contributed by rutvik_56
 
</script>

Producción:

Complejidad Temporal: O(1).

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta