Encuentra la suma del módulo K del primer N número natural

Dados dos enteros N y K , la tarea es encontrar la suma del módulo K de los primeros N números naturales, es decir, 1%K + 2%K + ….. + N%K.

Ejemplos: 

Input : N = 10 and K = 2.
Output : 5
Sum = 1%2 + 2%2 + 3%2 + 4%2 + 5%2 + 6%2 +
      7%2 + 8%2 + 9%2 + 10%2
   = 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0
   = 5.

Método 1: 

Iterar una variable i de 1 a N, evaluar y sumar i%K. 

A continuación se muestra la implementación de este enfoque:  

// C++ program to find sum of
// modulo K of first N natural numbers.
#include <bits/stdc++.h>
using namespace std;
 
// Return sum of modulo K of
// first N natural numbers.
int findSum(int N, int K)
{
    int ans = 0;
 
    // Iterate from 1 to N &&
    // evaluating and adding i % K.
    for (int i = 1; i <= N; i++)
        ans += (i % K);
 
    return ans;
}
 
// Driver Program
int main()
{
    int N = 10, K = 2;
    cout << findSum(N, K) << endl;
    return 0;
}

// Java program to find sum of modulo
// K of first N natural numbers.
import java.io.*;
 
class GFG {
 
    // Return sum of modulo K of
    // first N natural numbers.
    static int findSum(int N, int K)
    {
        int ans = 0;
 
        // Iterate from 1 to N && evaluating
        // and adding i % K.
        for (int i = 1; i <= N; i++)
            ans += (i % K);
 
        return ans;
    }
 
    // Driver program
    static public void main(String[] args)
    {
        int N = 10, K = 2;
        System.out.println(findSum(N, K));
    }
}
 
// This code is contributed by vt_m.

# Python3 program to find sum
# of modulo K of first N
# natural numbers.
 
# Return sum of modulo K of
# first N natural numbers.
 
def findSum(N, K):
    ans = 0;
 
    # Iterate from 1 to N &&
    # evaluating and adding i % K.
    for i in range(1, N + 1):
        ans += (i % K);
 
    return ans;
 
# Driver Code
N = 10;
K = 2;
print(findSum(N, K));
 
# This code is contributed by mits

// C# program to find sum of modulo
// K of first N natural numbers.
using System;
 
class GFG {
 
    // Return sum of modulo K of
    // first N natural numbers.
    static int findSum(int N, int K)
    {
        int ans = 0;
 
        // Iterate from 1 to N && evaluating
        // and adding i % K.
        for (int i = 1; i <= N; i++)
            ans += (i % K);
 
        return ans;
    }
 
    // Driver program
    static public void Main()
    {
        int N = 10, K = 2;
        Console.WriteLine(findSum(N, K));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find sum
// of modulo K of first N
// natural numbers.
 
 
// Return sum of modulo K of
// first N natural numbers.
 
function findSum($N, $K)
{
    $ans = 0;
 
    // Iterate from 1 to N &&
    // evaluating and adding i % K.
    for ($i = 1; $i <= $N; $i++)
        $ans += ($i % $K);
 
    return $ans;
}
 
// Driver Code
$N = 10; $K = 2;
echo findSum($N, $K), "\n";
 
// This code is contributed by ajit
?>

<script>
 
// JavaScript program to find sum
// of modulo K of first N natural
// numbers.
 
// Return sum of modulo K of
// first N natural numbers.
function findSum(N, K)
{
    let ans = 0;
 
    // Iterate from 1 to N && evaluating
    // and adding i % K.
    for(let i = 1; i <= N; i++)
        ans += (i % K);
 
    return ans;
}
 
// Driver Code
let N = 10, K = 2;
 
document.write(findSum(N, K));
 
// This code is contributed by code_hunt
 
</script>

Producción : 

5

Complejidad temporal: O(N).

Método 2: 
Dos casos surgen en este método.
Caso 1: Cuando N < K , para cada número i, N >= i >= 1, dará como resultado i al operar con módulo K. Entonces, la suma requerida será la suma del primer N número natural, N* (N+1)/2.
Caso 2: Cuando N >= K , entonces los números enteros de 1 a K en secuencia de números naturales producirán, 1, 2, 3, ….., K – 1, 0 como resultado cuando se opera con módulo K. Similarmente, de K + 1 a 2K, producirá el mismo resultado. Entonces, la idea es contar cuántas veces aparece esta secuencia y multiplicarla por la suma de los primeros K – 1 números naturales. 

A continuación se muestra la implementación de este enfoque:  

// C++ program to find sum of modulo
// K of first N natural numbers.
#include <bits/stdc++.h>
using namespace std;
 
// Return sum of modulo K of
// first N natural numbers.
int findSum(int N, int K)
{
    int ans = 0;
 
    // Counting the number of times 1, 2, ..,
    // K-1, 0 sequence occurs.
    int y = N / K;
 
    // Finding the number of elements left which
    // are incomplete of sequence Leads to Case 1 type.
    int x = N % K;
 
    // adding multiplication of number of
    // times 1, 2, .., K-1, 0 sequence occurs
    // and sum of first k natural number and sequence
    // from case 1.
    ans = (K * (K - 1) / 2) * y + (x * (x + 1)) / 2;
 
    return ans;
}
 
// Driver program
int main()
{
    int N = 10, K = 2;
    cout << findSum(N, K) << endl;
    return 0;
}

// Java program to find sum of modulo
// K of first N natural numbers.
import java.io.*;
 
class GFG {
 
    // Return sum of modulo K of
    // first N natural numbers.
    static int findSum(int N, int K)
    {
        int ans = 0;
 
        // Counting the number of times 1, 2, ..,
        // K-1, 0 sequence occurs.
        int y = N / K;
 
        // Finding the number of elements left which
        // are incomplete of sequence Leads to Case 1 type.
        int x = N % K;
 
        // adding multiplication of number of times
        // 1, 2, .., K-1, 0 sequence occurs and sum
        // of first k natural number and sequence
        // from case 1.
        ans = (K * (K - 1) / 2) * y + (x * (x + 1)) / 2;
 
        return ans;
    }
 
    // Driver program
    static public void main(String[] args)
    {
        int N = 10, K = 2;
        System.out.println(findSum(N, K));
    }
}
 
// This Code is contributed by vt_m.

# Python3 program to find sum of modulo
# K of first N natural numbers.
 
# Return sum of modulo K of
# first N natural numbers.
def findSum(N, K):
 
    ans = 0;
 
    # Counting the number of times
    # 1, 2, .., K-1, 0 sequence occurs.
    y = N / K;
 
    # Finding the number of elements
    # left which are incomplete of
    # sequence Leads to Case 1 type.
    x = N % K;
 
    # adding multiplication of number
    # of times 1, 2, .., K-1, 0
    # sequence occurs and sum of
    # first k natural number and
    # sequence from case 1.
    ans = ((K * (K - 1) / 2) * y +
                (x * (x + 1)) / 2);
 
    return int(ans);
 
# Driver Code
N = 10;
K = 2;
print(findSum(N, K));
 
# This code is contributed by mits

// C# program to find sum of modulo
// K of first N natural numbers.
using System;
 
class GFG {
 
    // Return sum of modulo K of
    // first N natural numbers.
    static int findSum(int N, int K)
    {
        int ans = 0;
 
        // Counting the number of times 1, 2, ..,
        // K-1, 0 sequence occurs.
        int y = N / K;
 
        // Finding the number of elements left which
        // are incomplete of sequence Leads to Case 1 type.
        int x = N % K;
 
        // adding multiplication of number of times
        // 1, 2, .., K-1, 0 sequence occurs and sum
        // of first k natural number and sequence
        // from case 1.
        ans = (K * (K - 1) / 2) * y + (x * (x + 1)) / 2;
 
        return ans;
    }
 
    // Driver program
    static public void Main()
    {
        int N = 10, K = 2;
        Console.WriteLine(findSum(N, K));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find sum of modulo
// K of first N natural numbers.
 
// Return sum of modulo K of
// first N natural numbers.
function findSum($N, $K)
{
    $ans = 0;
 
    // Counting the number of times
    // 1, 2, .., K-1, 0 sequence occurs.
    $y = $N / $K;
 
    // Finding the number of elements
    // left which are incomplete of
    // sequence Leads to Case 1 type.
    $x = $N % $K;
 
    // adding multiplication of number
    // of times 1, 2, .., K-1, 0
    // sequence occurs and sum of
    // first k natural number and
    // sequence from case 1.
    $ans = ($K * ($K - 1) / 2) * $y
                 + ($x * ($x + 1)) / 2;
 
    return $ans;
}
 
// Driver program
    $N = 10; $K = 2;
    echo findSum($N, $K) ;
 
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program to find sum of modulo
// K of first N natural numbers.
 
// Return sum of modulo K of
// first N natural numbers.
function findSum(N, K)
{
    let ans = 0;
 
    // Counting the number of times
    // 1, 2, .., K-1, 0 sequence occurs.
    let y = N / K;
 
    // Finding the number of elements
    // left which are incomplete of
    // sequence Leads to Case 1 type.
    let x = N % K;
 
    // adding multiplication of number
    // of times 1, 2, .., K-1, 0
    // sequence occurs and sum of
    // first k natural number and
    // sequence from case 1.
    ans = (K * (K - 1) / 2) * y +
          (x * (x + 1)) / 2;
 
    return ans;
}
 
// Driver code
let N = 10;
let K = 2;
 
document.write(findSum(N, K));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Producción : 

5

Complejidad temporal: O(1).

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.