Given two numbers N and K, the task is to find the sum of first K numbers which are not divisible by N.
Examples:
Input: N = 5, K = 10
Output: 63
Explanation: Sum of { 1, 2, 3, 4, 6, 7, 8, 9, 11, 12 } is 63.Input: N = 3, k = 13
Output: 127
Explanation: Sum of { 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19 } is 127.
Approach: In order to solve this problem, we need to follow the following steps:
- Calculate the last multiple of N by (K / (N – 1)) * N
- Calculate K%(N – 1). If the remainder is 0, (K / (N – 1)) * N – 1 gives the last value which is not divisible by N. Otherwise, we need to add the remainder to (K / (N – 1)) * N.
- Calculate the sum up to the last value which is not divisible by N obtained in the above step.
- Calculate the sum of multiples of N and subtract from the sum calculated in the above step to get the desired result.
Below code is the implementation of the above approach:
C++
// C++ Program to calculate// the sum of first K// numbers not divisible by N#include <bits/stdc++.h>using namespace std;// Function to find the sumint findSum(int n, int k){ // Find the last multiple of N int val = (k / (n - 1)) * n; int rem = k % (n - 1); // Find the K-th non-multiple of N if (rem == 0) { val = val - 1; } else { val = val + rem; } // Calculate the sum of // all elements from 1 to val int sum = (val * (val + 1)) / 2; // Calculate the sum of // all multiples of N // between 1 to val int x = k / (n - 1); int sum_of_multiples = (x * (x + 1) * n) / 2; sum -= sum_of_multiples; return sum;}// Driver codeint main(){ int n = 7, k = 13; cout << findSum(n, k) << endl;} |
Java
// Java program to calculate // the sum of first K numbers// not divisible by Nimport java.util.*;class GFG {// Function to find the sumstatic int findSum(int n, int k){ // Find the last multiple of N int val = (k / (n - 1)) * n; int rem = k % (n - 1); // Find the K-th non-multiple of N if (rem == 0) { val = val - 1; } else { val = val + rem; } // Calculate the sum of // all elements from 1 to val int sum = (val * (val + 1)) / 2; // Calculate the sum of // all multiples of N // between 1 to val int x = k / (n - 1); int sum_of_multiples = (x * (x + 1) * n) / 2; sum -= sum_of_multiples; return sum;}// Driver codepublic static void main(String[] args){ int n = 7, k = 13; System.out.println(findSum(n, k));}}// This code is contributed by offbeat |
Python3
# Python3 Program to calculate# the sum of first K# numbers not divisible by N# Function to find the sumdef findSum(n, k): # Find the last multiple of N val = (k // (n - 1)) * n; rem = k % (n - 1); # Find the K-th non-multiple of N if (rem == 0): val = val - 1; else: val = val + rem; # Calculate the sum of # all elements from 1 to val sum = (val * (val + 1)) // 2; # Calculate the sum of # all multiples of N # between 1 to val x = k // (n - 1); sum_of_multiples = (x * (x + 1) * n) // 2; sum -= sum_of_multiples; return sum;# Driver coden = 7; k = 13;print(findSum(n, k))# This code is contributed by Code_Mech |
C#
// C# program to calculate // the sum of first K numbers// not divisible by Nusing System;class GFG{// Function to find the sumstatic int findSum(int n, int k){ // Find the last multiple of N int val = (k / (n - 1)) * n; int rem = k % (n - 1); // Find the K-th non-multiple of N if (rem == 0) { val = val - 1; } else { val = val + rem; } // Calculate the sum of // all elements from 1 to val int sum = (val * (val + 1)) / 2; // Calculate the sum of // all multiples of N // between 1 to val int x = k / (n - 1); int sum_of_multiples = (x * (x + 1) * n) / 2; sum -= sum_of_multiples; return sum;}// Driver codepublic static void Main(String[] args){ int n = 7, k = 13; Console.WriteLine(findSum(n, k));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript Program to calculate// the sum of first K// numbers not divisible by N// Function to find the sumfunction findSum(n, k){ // Find the last multiple of N var val = parseInt(k / (n - 1)) * n; var rem = k % (n - 1); // Find the K-th non-multiple of N if (rem == 0) { val = val - 1; } else { val = val + rem; } // Calculate the sum of // all elements from 1 to val var sum = parseInt((val * (val + 1)) / 2); // Calculate the sum of // all multiples of N // between 1 to val var x = parseInt(k / (n - 1)); var sum_of_multiples = parseInt( (x * (x + 1) * n) / 2); sum -= sum_of_multiples; return sum;}// Driver codevar n = 7, k = 13;document.write(findSum(n, k))// This code is contributed by rrrtnx</script> |
Output:
99
Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach:
1. Initialize a variable sum to 0 to keep track of the sum of the numbers.
2. Initialize a counter variable count to 0 to keep track of the number of non-divisible numbers found so far.
3. Initialize a variable i to 1 to start iterating from the first positive integer.
4. Repeat the following steps until count reaches K:
a. Check if i is divisible by N. If it is, increment i and continue to the next iteration.
b. If i is not divisible by N, add it to sum and increment count.
c. Increment i to check the next positive integer.
Once count reaches K, sum will contain the sum of the first K numbers which are not divisible by N.
C
#include <stdio.h>int main() { int K = 5; int N = 2; int sum = 0; int count = 0; int i = 1; while (count < K) { if (i % N == 0) { i++; continue; } sum += i; count++; i++; } printf("Sum of first %d numbers not divisible by %d: %d\n", K, N, sum); return 0;} |
C++
#include <iostream>using namespace std;int main() { int K = 5; int N = 2; int sum = 0; int count = 0; int i = 1; while (count < K) { if (i % N == 0) { i++; continue; } sum += i; count++; i++; } cout << "Sum of first " << K << " numbers not divisible by " << N << ": " << sum << endl; return 0;} |
Java
import java.util.*;class Main { public static void main(String[] args) { int K = 5; int N = 2; // Initialize sum, count, and i to 0, 0, and 1, // respectively. int sum = 0; int count = 0; int i = 1; // While count is less than K, do the following: while (count < K) { // If i is divisible by N, increment i and // continue with the next iteration. if (i % N == 0) { i++; continue; } // Add i to sum, increment count and i. sum += i; count++; i++; } // Print the sum of the first K numbers not // divisible by N. System.out.println("Sum of first " + K + " numbers not divisible by " + N + ": " + sum); }} |
Python3
K = 5N = 2# Initialize sum, count, and i to 0, 0, and 1, respectively.sum = 0count = 0i = 1# While count is less than K, do the following:while count < K: # If i is divisible by N, increment i and continue with the next iteration. if i % N == 0: i += 1 continue # Add i to sum, increment count and i. sum += i count += 1 i += 1# Print the sum of the first K numbers not divisible by N.print("Sum of first", K, "numbers not divisible by", N, ":", sum) |
C#
using System;class GFG { public static void Main(string[] args) { int K = 5; int N = 2; // Initialize sum, count, and i to 0, 0, and 1, // respectively. int sum = 0; int count = 0; int i = 1; // While count is less than K, do the following: while (count < K) { // If i is divisible by N, increment i and // continue with the next iteration. if (i % N == 0) { i++; continue; } // Add i to sum, increment count and i. sum += i; count++; i++; } // Print the sum of the first K numbers not // divisible by N. Console.Write("Sum of first " + K + " numbers not divisible by " + N + ": " + sum); }}// this code is contributed by shivanisinghss2110 |
Javascript
// Javascript code addition let K = 5;let N = 2;let sum = 0;let count = 0;let i = 1;while (count < K) { if (i % N == 0) { i++; continue; } sum += i; count++; i++;}console.log("Sum of first " + K + " numbers not divisible by " + N + " : " + sum);// The code is contributed by Arushi Jindal. |
Output
Sum of first 5 numbers not divisible by 2: 25
Time Complexity: O(K) where K is the number of non-divisible numbers to find.
Auxiliary Space: O(1) since we only need to store a few variables.
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]
[…] Read More Info here to that Topic: geeksforgeeks.org/sum-of-first-k-numbers-which-are-not-divisible-by-n/ […]