Given a number N. The task is to find the sum of all those numbers from 1 to N that are divisible by 2 or by 7.
Examples:
Input : N = 7
Output : 19
sum = 2 + 4 + 6 + 7
Input : N = 14
Output : 63
sum = 2 + 4 + 6 + 7 + 8 + 10 + 12 + 14
Brute Force Approach:
A brute force approach to solve this problem would be to loop through all the numbers from 1 to N, and for each number, check if it is divisible by 2 or 7. If it is, then add it to the result. At the end of the loop, return the result.
Below is the implementation of the above approach:
C++
// C++ program to find sum of numbers from 1 to N// which are divisible by 2 or 7#include <bits/stdc++.h>using namespace std;// Function to calculate the sum// of numbers divisible by 2 or 7int sum(int N){ int ans = 0; for(int i = 1; i <= N; i++){ if(i % 2 == 0 || i % 7 == 0){ ans += i; } } return ans;}// Driver codeint main(){ int N = 20; cout << sum(N); return 0;} |
Java
public class Main { // Driver Code public static void main(String[] args) { int N = 20; int result = sum(N); System.out.println(result); } public static int sum(int N) { int ans = 0; for (int i = 1; i <= N; i++) { if (i % 2 == 0 || i % 7 == 0) { ans += i; } } return ans; }} |
Python3
# Python program to find sum of numbers from 1 to N# which are divisible by 2 or 7# Function to calculate the sum# of numbers divisible by 2 or 7def sum(N): ans = 0 for i in range(1, N+1): if i % 2 == 0 or i % 7 == 0: ans += i return ans# Driver codeif __name__ == "__main__": N = 20 print(sum(N))# The code is contributed by Nidhi goel. |
C#
using System;class Program{ // Function to calculate the sum // of numbers divisible by 2 or 7 static int Sum(int N) { int ans = 0; for (int i = 1; i <= N; i++) { if (i % 2 == 0 || i % 7 == 0) { ans += i; } } return ans; } // Driver code static void Main() { int N = 20; Console.WriteLine(Sum(N)); }} |
Javascript
// Function to calculate the sum of numbers divisible by 2 or 7function sum(N) { let ans = 0; for (let i = 1; i <= N; i++) { if (i % 2 == 0 || i % 7 == 0) { ans += i; } } return ans;}let N = 20;console.log(sum(N)); |
117
Time Complexity: O(N)
Space Complexity: O(1)
Approach: To solve the problem, follow the below steps:
->Find the sum of numbers that are divisible by 2 upto N. Denote it by S1.
->Find the sum of numbers that are divisible by 7 upto N. Denote it by S2.
->Find the sum of numbers that are divisible by 14(2*7) upto N. Denote it by S3.
->The final answer will be S1 + S2 – S3.
In order to find the sum, we can use the general formula of A.P. which is:
Sn = (n/2) * {2*a + (n-1)*d}
For S1: The total numbers that will be divisible by 2 upto N will be N/2 and the series will be 2, 4, 6, 8, ….
Hence,
S1 = ((N/2)/2) * (2 * 2 + (N/2 - 1) * 2)
For S2: The total numbers that will be divisible by 7 up to N will be N/7 and the series will be 7, 14, 21, 28, ……
Hence,
S2 = ((N/7)/2) * (2 * 7 + (N/7 - 1) * 7)
For S3: The total numbers that will be divisible by 14 upto N will be N/14.
Hence,
S3 = ((N/14)/2) * (2 * 14 + (N/14 - 1) * 14)
Therefore, the result will be:
S = S1 + S2 - S3
Below is the implementation of the above approach:
C++
// C++ program to find sum of numbers from 1 to N// which are divisible by 2 or 7#include <bits/stdc++.h>using namespace std;// Function to calculate the sum// of numbers divisible by 2 or 7int sum(int N){ int S1, S2, S3; S1 = ((N / 2)) * (2 * 2 + (N / 2 - 1) * 2) / 2; S2 = ((N / 7)) * (2 * 7 + (N / 7 - 1) * 7) / 2; S3 = ((N / 14)) * (2 * 14 + (N / 14 - 1) * 14) / 2; return S1 + S2 - S3;}// Driver codeint main(){ int N = 20; cout << sum(N); return 0;} |
Java
// Java program to find sum of // numbers from 1 to N which // are divisible by 2 or 7 import java.io.*;class GFG {// Function to calculate the sum // of numbers divisible by 2 or 7 public static int sum(int N) { int S1, S2, S3; S1 = ((N / 2)) * (2 * 2 + (N / 2 - 1) * 2) / 2; S2 = ((N / 7)) * (2 * 7 + (N / 7 - 1) * 7) / 2; S3 = ((N / 14)) * (2 * 14 + (N / 14 - 1) * 14) / 2; return S1 + S2 - S3; } // Driver code public static void main (String[] args) { int N = 20; System.out.println( sum(N)); } } // This code is contributed by ajit |
Python3
# Python3 implementation of # above approach# Function to calculate the sum # of numbers divisible by 2 or 7 def sum(N): S1 = ((N // 2)) * (2 * 2 + (N // 2 - 1) * 2) // 2 S2 = ((N // 7)) * (2 * 7 + (N // 7 - 1) * 7) // 2 S3 = ((N // 14)) * (2 * 14 + (N // 14 - 1) * 14) // 2 return S1 + S2 - S3# Driver code if __name__=='__main__': N = 20 print(sum(N))# This code is written by# Sanjit_Prasad |
C#
// C# program to find sum of // numbers from 1 to N which// are divisible by 2 or 7using System;class GFG{// Function to calculate the sum// of numbers divisible by 2 or 7public static int sum(int N){ int S1, S2, S3; S1 = ((N / 2)) * (2 * 2 + (N / 2 - 1) * 2) / 2; S2 = ((N / 7)) * (2 * 7 + (N / 7 - 1) * 7) / 2; S3 = ((N / 14)) * (2 * 14 + (N / 14 - 1) * 14) / 2; return S1 + S2 - S3;}// Driver codepublic static int Main(){ int N = 20; Console.WriteLine( sum(N)); return 0;}}// This code is contributed // by SoumikMondal |
Javascript
<script>// javascript program to find sum of // numbers from 1 to N which // are divisible by 2 or 7 // Function to calculate the sum // of numbers divisible by 2 or 7 function sum(N) { var S1, S2, S3; S1 = (((N / 2)) * parseInt(2 * 2 + parseInt(N / 2 - 1) * 2) / 2); S2 = (parseInt(parseInt(N / 7)) * (2 * 7 + parseInt(N / 7 - 1) * 7) / 2); S3 = (parseInt(parseInt(N / 14)) * (2 * 14 + parseInt(N / 14 - 1) * 14) / 2); return S1 + S2 - S3; } // Driver code var N = 20; document.write( sum(N)); // This code is contributed by shikhasingrajput </script> |
PHP
<?php// PHP program to find sum of numbers // from 1 to N which are divisible by 2 or 7 // Function to calculate the sum // of numbers divisible by 2 or 7 function sum($N) { $S1 = (int)(($N / 2)) * (int)(2 * 2 + (int)($N / 2 - 1) * 2) / 2; $S2 = (int)(($N / 7)) * (int)(2 * 7 + (int)($N / 7 - 1) * 7) / 2; $S3 = (int)(($N / 14)) * (int)(2 * 14 + (int)($N / 14 - 1) * 14) / 2; return ($S1 + $S2) - $S3; } // Driver code $N = 20; echo sum($N); // This Code is Contributed by akt_mit?> |
117
Time Complexity: O(1), since there is no loop or recursion.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
