Given three integers N, K, and R. The task is to calculate the sum of all those numbers from 1 to N which yields remainder R upon division by K.
Examples:
Input: N = 20, K = 4, R = 3
Output: 55
3, 7, 11, 15 and 19 are the only numbers that give 3 as the remainder on division with 4.
3 + 7 + 11 + 15 + 19 = 55
Input: N = 15, K = 13, R = 2
Output: 17
Approach:
- Initialize sum = 0 and take the modulo of each element from 1 to N with K.
- If the remainder is equal to R, then update sum = sum + i where i is the current number that gave R as the remainder on dividing by K.
- Print the value of sum in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the sumlong long int count(int N, int K, int R){ long long int sum = 0; for (int i = 1; i <= N; i++) { // If current number gives R as the // remainder on dividing by K if (i % K == R) // Update the sum sum += i; } // Return the sum return sum;}// Driver codeint main(){ int N = 20, K = 4, R = 3; cout << count(N, K, R); return 0;} |
Java
// Java implementation of the approach class GfG { // Function to return the sum static long count(int N, int K, int R) { long sum = 0; for (int i = 1; i <= N; i++) { // If current number gives R as the // remainder on dividing by K if (i % K == R) // Update the sum sum += i; } // Return the sum return sum; } // Driver code public static void main(String[] args) { int N = 20, K = 4, R = 3; System.out.println(count(N, K, R)); }} // This code is contributed by// prerna saini. |
Python3
# Python 3 implementation of the approach# Function to return the sumdef count(N, K, R): sum = 0 for i in range(1, N + 1): # If current number gives R as the # remainder on dividing by K if (i % K == R): # Update the sum sum += i # Return the sum return sum# Driver codeif __name__ == '__main__': N = 20 K = 4 R = 3 print(count(N, K, R))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approach using System;class GFG { // Function to return the sum static long count(int N, int K, int R) { long sum = 0; for (int i = 1; i <= N; i++) { // If current number gives R as the // remainder on dividing by K if (i % K == R) // Update the sum sum += i; } // Return the sum return sum; } // Driver code public static void Main() { int N = 20, K = 4, R = 3; Console.Write(count(N, K, R)); }} // This code is contributed by// Akanksha Rai |
PHP
<?php// PHP implementation of the approach// Function to return the sumfunction count1($N, $K, $R){ $sum = 0; for ($i = 1; $i <= $N; $i++) { // If current number gives R as the // remainder on dividing by K if ($i % $K == $R) // Update the sum $sum += $i; } // Return the sum return $sum;}// Driver code$N = 20; $K = 4; $R = 3;echo count1($N, $K, $R);// This code is contributed// by Akanksha Rai?> |
Javascript
<script>// Javascript implementation of the approach // Function to return the sum function count(N , K , R) { var sum = 0; for (i = 1; i <= N; i++) { // If current number gives R as the // remainder on dividing by K if (i % K == R) // Update the sum sum += i; } // Return the sum return sum; } // Driver code var N = 20, K = 4, R = 3; document.write(count(N, K, R));// This code contributed by aashish1995</script> |
Output:
55
Time Complexity: O(N)
Auxiliary Space: O(1), since no extra space has been taken.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/sum-of-the-natural-numbers-up-to-n-whose-modulo-with-k-yield-r/ […]