Divisible and Non-divisible Sums Difference solution and explanation
Google
9 more videos on this problem
Leetcode | 2894. Divisible and Non-divisible Sums Difference | Easy | Java SolutionDeveloper Docs · 3:48 · 921 views
Daily Leetcode #1883: May 27, 2025 - 2894. Divisible and Non-divisible Sums DifferenceProgramming Live with Larry · 8:33 · 284 views
Divisible and Non-divisible Sums Difference (LeetCode Problem 2894)Brodmann38 · 5:31 · 272 views
2894. Divisible and Non-divisible Sums Difference | Leetcode Daily - PythonLeetcode Daily · 6:14 · 225 views
Divisible and Non divisible Sums Difference - Leetcode 2894 - PythonTim Huang · 3:49 · 171 views
Leetcode 2894 Divisible and Non-divisible Sums DifferenceTech Diet · 3:27 · 154 views
Divisible and Non-divisible Sums Difference [Leetcode-2894]DSA_decoded · 2:14 · 144 views
2894 Divisible and Non divisible Sums Difference | LeetCodeR Sai Siddhu · 2:56 · 68 views
LeetCode 2894. Divisible and Non-divisible Sums DifferenceEdTech · 12:41 · 63 views
2894. Divisible and Non-divisible Sums Difference | O(n) + O(1) Solution 🔥 27-05-25LeetCode Daily LIVE · 10:29 · 37 views
The problem
You are given positive integers n and m.
Define two integers as follows:
num1: The sum of all integers in the range[1, n](both inclusive) that are not divisible bym.num2: The sum of all integers in the range[1, n](both inclusive) that are divisible bym.
Return the integer num1 - num2.
Example 1:
Input: n = 10, m = 3 Output: 19 Explanation: In the given example: - Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37. - Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18. We return 37 - 18 = 19 as the answer.
Example 2:
Input: n = 5, m = 6 Output: 15 Explanation: In the given example: - Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15. - Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0. We return 15 - 0 = 15 as the answer.
Example 3:
Input: n = 5, m = 1 Output: -15 Explanation: In the given example: - Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0. - Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15. We return 0 - 15 = -15 as the answer.
Constraints:
1 <= n, m <= 1000
Approach overview
Problem Overview: Given two integers n and m, compute the difference between the sum of numbers from 1..n that are not divisible by m and the sum of numbers that are divisible by m. The result is sumNonDivisible - sumDivisible.
Approach 1: Iterative Calculation (O(n) time, O(1) space)
Iterate through every number from 1 to n. For each value i, check the divisibility condition using i % m. If the remainder is zero, add i to the divisible sum; otherwise add it to the non‑divisible sum. After the loop finishes, subtract the two totals. This approach mirrors the problem statement directly and is easy to implement in any language. It works well when n is small or when clarity matters more than micro‑optimizations. The algorithm uses constant memory and a single pass through the range.
Approach 2: Formula-based Optimization (O(1) time, O(1) space)
The optimized approach relies on arithmetic series formulas from math. First compute the sum of all numbers from 1..n using total = n * (n + 1) / 2. Next count how many numbers are divisible by m: k = n / m. Those numbers are m, 2m, 3m ... km. Their sum forms another arithmetic series: sumDivisible = m * (k * (k + 1) / 2). The non‑divisible sum is simply total - sumDivisible. The required difference becomes (total - sumDivisible) - sumDivisible, which simplifies to total - 2 * sumDivisible. This eliminates iteration entirely and runs in constant time using simple arithmetic operations, a common trick in number theory style problems.
Recommended for interviews: Start with the iterative approach to show you understand the requirement and the divisibility check. Then optimize using the arithmetic formula. Interviewers usually expect the constant‑time mathematical solution because it demonstrates pattern recognition and familiarity with sum formulas.
Approach 1: Iterative Approach
This approach involves iterating through every number from 1 to n and checking whether each number is divisible by m. Based on this check, we add the number to either num1 or num2. Finally, calculate the result as num1 - num2.
def divisible_non_divisible_difference(n, m):
num1, num2 = 0, 0
for i in range(1, n + 1):
if i % m == 0:
num2 += i
else:
num1 += i
return num1 - num2
n, m = 10, 3
print(divisible_non_divisible_difference(n, m))public class Main {
public static int divisibleNonDivisibleDifference(int n, int m) {
int num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (i % m == 0) {
num2 += i;
} else {
num1 += i;
}
}
return num1 - num2;
}
public static void main(String[] args) {
int n = 10, m = 3;
System.out.println(divisibleNonDivisibleDifference(n, m));
}
}#include <iostream>
int divisibleNonDivisibleDifference(int n, int m) {
int num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (i % m == 0) {
num2 += i;
} else {
num1 += i;
}
}
return num1 - num2;
}
int main() {
int n = 10, m = 3;
std::cout << divisibleNonDivisibleDifference(n, m) << std::endl;
return 0;
}function divisibleNonDivisibleDifference(n, m) {
let num1 = 0, num2 = 0;
for (let i = 1; i <= n; i++) {
if (i % m === 0) {
num2 += i;
} else {
num1 += i;
}
}
return num1 - num2;
}
let n = 10, m = 3;
console.log(divisibleNonDivisibleDifference(n, m));#include <stdio.h>
int divisibleNonDivisibleDifference(int n, int m) {
int num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (i % m == 0) {
num2 += i;
} else {
num1 += i;
}
}
return num1 - num2;
}
int main() {
int n = 10, m = 3;
printf("%d\n", divisibleNonDivisibleDifference(n, m));
return 0;
}using System;
class Program {
static int DivisibleNonDivisibleDifference(int n, int m) {
int num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (i % m == 0) {
num2 += i;
} else {
num1 += i;
}
}
return num1 - num2;
}
static void Main() {
int n = 10, m = 3;
Console.WriteLine(DivisibleNonDivisibleDifference(n, m));
}
}Uses a simple loop from 1 to n for summing numbers based on their divisibility by m using if-else conditions, eventually calculating num1 - num2.
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Formula-based Optimization
This approach uses arithmetic series formulas to calculate the sums directly rather than iterating through each element. The sum of numbers divisible by m can be expressed in terms of another arithmetic series with step m.
def sum_of_divisibles(n, m):
p = n // m
return m * (p * (p + 1)) // 2
def formula_based_difference(n, m):
total_sum = n * (n + 1) // 2
sum_divisibles = sum_of_divisibles(n, m)
sum_non_divisibles = total_sum - sum_divisibles
return sum_non_divisibles - sum_divisibles
n, m = 10, 3
print(formula_based_difference(n, m))public class Main {
public static int sumOfDivisibles(int n, int m) {
int p = n / m;
return m * (p * (p + 1)) / 2;
}
public static int formulaBasedDifference(int n, int m) {
int totalSum = n * (n + 1) / 2;
int sumDivisibles = sumOfDivisibles(n, m);
int sumNonDivisibles = totalSum - sumDivisibles;
return sumNonDivisibles - sumDivisibles;
}
public static void main(String[] args) {
int n = 10, m = 3;
System.out.println(formulaBasedDifference(n, m));
}
}#include <iostream>
int sumOfDivisibles(int n, int m) {
int p = n / m;
return m * (p * (p + 1)) / 2;
}
int formulaBasedDifference(int n, int m) {
int totalSum = n * (n + 1) / 2;
int sumDivisibles = sumOfDivisibles(n, m);
int sumNonDivisibles = totalSum - sumDivisibles;
return sumNonDivisibles - sumDivisibles;
}
int main() {
int n = 10, m = 3;
std::cout << formulaBasedDifference(n, m) << std::endl;
return 0;
}function sumOfDivisibles(n, m) {
let p = Math.floor(n / m);
return m * (p * (p + 1)) / 2;
}
function formulaBasedDifference(n, m) {
let totalSum = n * (n + 1) / 2;
let sumDivisibles = sumOfDivisibles(n, m);
let sumNonDivisibles = totalSum - sumDivisibles;
return sumNonDivisibles - sumDivisibles;
}
let n = 10, m = 3;
console.log(formulaBasedDifference(n, m));#include <stdio.h>
int sumOfDivisibles(int n, int m) {
int p = n / m;
return m * (p * (p + 1)) / 2;
}
int formulaBasedDifference(int n, int m) {
int totalSum = n * (n + 1) / 2;
int sumDivisibles = sumOfDivisibles(n, m);
int sumNonDivisibles = totalSum - sumDivisibles;
return sumNonDivisibles - sumDivisibles;
}
int main() {
int n = 10, m = 3;
printf("%d\n", formulaBasedDifference(n, m));
return 0;
}using System;
class Program {
static int SumOfDivisibles(int n, int m) {
int p = n / m;
return m * (p * (p + 1)) / 2;
}
static int FormulaBasedDifference(int n, int m) {
int totalSum = n * (n + 1) / 2;
int sumDivisibles = SumOfDivisibles(n, m);
int sumNonDivisibles = totalSum - sumDivisibles;
return sumNonDivisibles - sumDivisibles;
}
static void Main() {
int n = 10, m = 3;
Console.WriteLine(FormulaBasedDifference(n, m));
}
}By leveraging arithmetic progressions, this method calculates total_sum and sum_divisibles directly, computing the differences once all such sums are available.
Time Complexity: O(1). Space Complexity: O(1).
Approach 3: Simulation
We traverse every number in the range [1, n]. If it is divisible by m, we subtract it from the answer. Otherwise, we add it to the answer.
After the traversal, we return the answer.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
function differenceOfSums(n: number, m: number): number {
let ans = 0;
for (let i = 1; i <= n; ++i) {
ans += i % m ? i : -i;
}
return ans;
}func differenceOfSums(n int, m int) (ans int) {
for i := 1; i <= n; i++ {
if i%m == 0 {
ans -= i
} else {
ans += i
}
}
return
}impl Solution {
pub fn difference_of_sums(n: i32, m: i32) -> i32 {
let mut ans = 0;
for i in 1..=n {
if i % m != 0 {
ans += i;
} else {
ans -= i;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n). Space Complexity: O(1). |
| Formula-based Optimization | Time Complexity: O(1). Space Complexity: O(1). |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Calculation | O(n) | O(1) | Simple implementation or when directly simulating the condition |
| Formula-based Optimization | O(1) | O(1) | Best for large n and interviews requiring mathematical optimization |
Frequently asked questions
Is Divisible and Non-divisible Sums Difference easy or hard?
Divisible and Non-divisible Sums Difference is classified as an Easy problem with a very high acceptance rate. The main challenge is recognizing that the iterative solution can be optimized using arithmetic sum formulas.
Divisible and Non-divisible Sums Difference Python/Java solution
Both Python and Java implementations typically use either a loop from 1 to n with a modulo check or the optimized formula. The formula-based approach calculates total = n*(n+1)/2 and subtracts twice the sum of multiples of m, achieving O(1) time complexity.
How to solve Divisible and Non-divisible Sums Difference in O(1)?
Use arithmetic series formulas. First compute total = n(n+1)/2. Count how many numbers are divisible by m as k = n // m, then compute their sum as m * (k(k+1)/2). The final answer is total - 2 * sumDivisible, which avoids looping entirely.
What is the best approach for Divisible and Non-divisible Sums Difference?
The optimal approach uses a mathematical formula instead of iteration. Compute the total sum from 1..n using n(n+1)/2, calculate the sum of multiples of m using m * (k(k+1)/2) where k = floor(n/m), and return total - 2 * sumDivisible. This runs in O(1) time and O(1) space.
Is Divisible and Non-divisible Sums Difference asked at Google/Amazon/Meta?
This problem is categorized as an Easy math problem and reflects patterns sometimes used in screening rounds or coding assessments. While the exact question may not frequently appear at Google or Meta, similar arithmetic or number‑theory optimization questions are common in interviews.
What data structure is used in Divisible and Non-divisible Sums Difference?
No special data structure is required. The solution relies purely on arithmetic calculations and integer variables. The optimized version mainly uses mathematical formulas from basic math and number theory.
What is the time complexity of Divisible and Non-divisible Sums Difference?
Two common solutions exist. The straightforward iterative method checks each number from 1 to n and runs in O(n) time with O(1) space. The optimized mathematical solution uses arithmetic series formulas and runs in O(1) time with constant space.