# Find sum of modulo K of first N natural number

Given two integer N ans K, the task is to find sum of modulo K of first N natural numbers i.e 1%K + 2%K + ….. + N%K.

Examples :

```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.
```

Method 1:
Iterate a varible i from 1 to N, evaluate and add i%K.

Below is the implementation of this approach:

## C++

 `// C++ program to find sum of ` `// modulo K of first N natural numbers. ` `#include ` `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

 `// 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

 `# 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#

 `// 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

 ` `

Output :

```5
```

Time Complexity : O(N).

Method 2 :
Two cases arise in this method.

Case 1: When N < K, for each number i, N >= i >= 1, will give i as result when operate with modulo K. So, required sum will be sum of first N natural number, N*(N+1)/2.

Case 2: When N >= K, then integers from 1 to K in natural number sequence will produce, 1, 2, 3, ….., K – 1, 0 as result when operate with modulo K. Similarly, from K + 1 to 2K, it will produce same result. So, the idea is to count how many number of times this sequence appears and multiply it with sum of first K – 1 natural numbers.
Below is the implementation of this approach:

## C++

 `// C++ program to find sum of modulo ` `// K of first N natural numbers. ` `#include ` `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

 `// 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

 `# 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#

 `// 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

 ` `

Output :

```5
```

Time Complexity : O(1).