Sum of numbers from 1 to N which are divisible by 3 or 4
Given a number N. The task is to find the sum of all those numbers from 1 to N that are divisible by 3 or by 4.
Examples:
Input : N = 5 Output : 7 sum = 3 + 4 Input : N = 12 Output : 42 sum = 3 + 4 + 6 + 8 + 9 + 12
Approach: To solve the problem, follow the below steps:
- Find the sum of numbers that are divisible by 3 upto N. Denote it by S1.
- Find the sum of numbers that are divisible by 4 upto N. Denote it by S2.
- Find the sum of numbers that are divisible by 12(3*4) 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} Where, n -> total number of terms a -> first term d -> common difference
For S1: The total numbers that will be divisible by 3 upto N will be N/3 and the series will be 3, 6, 9, 12, ….
Hence, S1 = ((N/3)/2) * (2 * 3 + (N/3 - 1) * 3)
For S2: The total numbers that will be divisible by 4 up to N will be N/4 and the series will be 4, 8, 12, 16, …...
Hence, S2 = ((N/4)/2) * (2 * 4 + (N/4 - 1) * 4)
For S3: The total numbers that will be divisible by 12 upto N will be N/12.
Hence, S3 = ((N/12)/2) * (2 * 12 + (N/12 - 1) * 12)
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 3 or 4 #include <bits/stdc++.h> using namespace std; // Function to calculate the sum // of numbers divisible by 3 or 4 int sum( int N) { int S1, S2, S3; S1 = ((N / 3)) * (2 * 3 + (N / 3 - 1) * 3) / 2; S2 = ((N / 4)) * (2 * 4 + (N / 4 - 1) * 4) / 2; S3 = ((N / 12)) * (2 * 12 + (N / 12 - 1) * 12) / 2; return S1 + S2 - S3; } // Driver code int main() { int N = 20; cout << sum(12); return 0; } |
Java
// Java program to find sum of numbers from 1 to N // which are divisible by 3 or 4 class GFG{ // Function to calculate the sum // of numbers divisible by 3 or 4 static int sum( int N) { int S1, S2, S3; S1 = ((N / 3 )) * ( 2 * 3 + (N / 3 - 1 ) * 3 ) / 2 ; S2 = ((N / 4 )) * ( 2 * 4 + (N / 4 - 1 ) * 4 ) / 2 ; S3 = ((N / 12 )) * ( 2 * 12 + (N / 12 - 1 ) * 12 ) / 2 ; return S1 + S2 - S3; } // Driver code public static void main (String[] args) { int N = 20 ; System.out.print(sum( 12 )); } } |
Python3
# Python3 program to find sum of numbers # from 1 to N # which are divisible by 3 or 4 # Function to calculate the sum # of numbers divisible by 3 or 4 def sum (N): global S1,S2,S3 S1 = (((N / / 3 )) * ( 2 * 3 + (N / / 3 - 1 ) * 3 ) / / 2 ) S2 = (((N / / 4 )) * ( 2 * 4 + (N / / 4 - 1 ) * 4 ) / / 2 ) S3 = (((N / / 12 )) * ( 2 * 12 + (N / / 12 - 1 ) * 12 ) / / 2 ) return int (S1 + S2 - S3) if __name__ = = '__main__' : N = 12 print ( sum (N)) # This code is contributed by Shrikant13 |
C#
// C# program to find sum of // numbers from 1 to N which // are divisible by 3 or 4 using System; class GFG { // Function to calculate the sum // of numbers divisible by 3 or 4 static int sum( int N) { int S1, S2, S3; S1 = ((N / 3)) * (2 * 3 + (N / 3 - 1) * 3) / 2; S2 = ((N / 4)) * (2 * 4 + (N / 4 - 1) * 4) / 2; S3 = ((N / 12)) * (2 * 12 + (N / 12 - 1) * 12) / 2; return S1 + S2 - S3; } // Driver code public static void Main () { int N = 20; Console.WriteLine(sum(12)); } } // This code is contributed // by inder_verma |
PHP
<?php // PHP program to find sum of // numbers from 1 to N which // are divisible by 3 or 4 // Function to calculate the sum // of numbers divisible by 3 or 4 function sum( $N ) { $S1 ; $S2 ; $S3 ; $S1 = (( $N / 3)) * (2 * 3 + ( $N / 3 - 1) * 3) / 2; $S2 = (( $N / 4)) * (2 * 4 + ( $N / 4 - 1) * 4) / 2; $S3 = (( $N / 12)) * (2 * 12 + ( $N / 12 - 1) * 12) / 2; return $S1 + $S2 - $S3 ; } // Driver Code $N = 20; echo sum(12); // This code is contributed // by inder_verma ?> |
Javascript
<script> // Javascript program to find sum of numbers from 1 to N // which are divisible by 3 or 4 // Function to calculate the sum // of numbers divisible by 3 or 4 function sum(N) { var S1, S2, S3; S1 = ((N / 3)) * (2 * 3 + (N / 3 - 1) * 3) / 2; S2 = ((N / 4)) * (2 * 4 + (N / 4 - 1) * 4) / 2; S3 = ((N / 12)) * (2 * 12 + (N / 12 - 1) * 12) / 2; return S1 + S2 - S3; } // Driver code var N = 20; document.write( sum(12)); </script> |
42
Time Complexity: O(1), since there is no loop or recursion.
Auxiliary Space: O(1), since no extra space has been taken.
Another Approach:
Declare two integer variables n and sum, and initialize n to the value 100 for the purpose of example.
Use a for loop to iterate from 1 to n, where the variable i is the loop counter.
For each iteration, check whether i is divisible by 3 or 4 using the modulo operator %. If the condition is true, add i to the variable sum.
After the loop has completed, print out the value of sum using printf.
Return 0 to indicate that the program has executed successfully.
C
#include <stdio.h> int main() { int n = 100; // assuming n is 100 for example purposes int sum = 0; for ( int i = 1; i <= n; i++) { if (i % 3 == 0 || i % 4 == 0) { sum += i; } } printf ( "Sum of numbers from 1 to %d which are divisible by 3 or 4 is %d\n" , n, sum); return 0; } |
Java
// Java program for the above approach public class Main { public static void main(String[] args) { int n = 100 ; // assuming n is 100 for example purposes int sum = 0 ; for ( int i = 1 ; i <= n; i++) { if (i % 3 == 0 || i % 4 == 0 ) { sum += i; } } System.out.printf( "Sum of numbers from 1 to %d which are divisible by 3 or 4 is %d\n" , n, sum); } } // Contributed by adityasha4x71 |
Python3
# Python program for the above approach n = 100 # assuming n is 100 for example purposes sum = 0 for i in range ( 1 , n + 1 ): if i % 3 = = 0 or i % 4 = = 0 : sum + = i print (f "Sum of numbers from 1 to {n} which are divisible by 3 or 4 is {sum}" ) |
C++
#include <iostream> using namespace std; int main() { int n = 100; // assuming n is 100 for example purposes int sum = 0; // Loop through all numbers from 1 to n for ( int i = 1; i <= n; i++) { // Check if the current number is divisible by 3 or // 4 if (i % 3 == 0 || i % 4 == 0) { // If the current number is divisible by 3 or 4, // add it to the sum sum += i; } } // Print the sum of all numbers divisible by 3 or 4 cout << "Sum of numbers from 1 to " << n << " which are divisible by 3 or 4 is " << sum << endl; return 0; } // This code is contributed by sarojmcy2e |
C#
using System; public class MainClass { public static void Main() { int n = 100; // assuming n is 100 for example purposes int sum = 0; for ( int i = 1; i <= n; i++) { if (i % 3 == 0 || i % 4 == 0) { sum += i; } } Console.WriteLine($ "Sum of numbers from 1 to {n} which are divisible by 3 or 4 is {sum}" ); } } |
Javascript
const n = 100; // assuming n is 100 for example purposes let sum = 0; for (let i = 1; i <= n; i++) { if (i % 3 === 0 || i % 4 === 0) { sum += i; } } console.log(`Sum of numbers from 1 to ${n} which are divisible by 3 or 4 is ${sum}`); |
Sum of numbers from 1 to 100 which are divisible by 3 or 4 is 2551
The time complexity of this program is O(n), where n is the upper limit of the range of numbers to be considered.
The space complexity is O(1), as the memory usage is constant regardless of the value of n.