DEV Community

Cover image for 🧠 Solving LeetCode Until I Become Top 1% — Day `1`
Md. Rishat Talukder
Md. Rishat Talukder

Posted on

🧠 Solving LeetCode Until I Become Top 1% — Day `1`

I don't know If this is a good decision or not... As a man who likes Probabilitis, there's one 2 in this case:

  • I go CRAZY🫠. or
  • I Become THE BEST PROGRAMMER IN THE WORLD🐵

SOUNDS GOOD TO ME!!

🧠 Solving LeetCode Until I Become Top 1% — Day 1

🔹 Problem: Divisible and Non-Divisible Sums Difference

Difficulty: Easy
Tags: Math

📝 Problem Summary

We have to find the difference between the sums of two arrays num1 and num2, with elements from 1 to n. num1 contains numbers not divisible by m, and num2 contains numbers divisible by m. The result should be the difference between the sums of num1 and num2.

🧠 My Thought Process

  • Brute Force Idea: Iterate through both arrays, calculate the sums while checking divisibility, and return the difference.

Time Complexity: O(n)

But as this is a math problem, I thought there might be a faster way to solve it.

  • Optimized Strategy: Since both arrays consist of elements from 1 to n, depending on divisibility, there are key properties we can use to calculate the sums directly without iterating through all elements.

Key Observations:

  • We can find the sum of num1 by subtracting the sum of numbers divisible by m from the total sum of numbers from 1 to n.

  • The count of numbers divisible by m in the range 1 to n is n // m.

  • To find the sum of numbers divisible by m, let’s say m = 2. The numbers divisible by m are 2, 4, 6, ..., n (if n is even) or 2, 4, 6, ..., n-1 (if n is odd).

    • This can be rewritten as 2 * (1 + 2 + 3 + ... + k), where k = n // m.
    • So the sum of numbers divisible by m is m * (k * (k + 1)) // 2.

  • The formula for the sum of the first n natural numbers is n * (n + 1) // 2.

  • Therefore, the sum of numbers not divisible by m is total_sum - sum_of_divisible_by_m.

  • The sum of num2 is just the sum of numbers divisible by m, which we've already calculated.

    • Algorithm Used: Math — Using properties of arithmetic series to calculate sums directly.

⚙️ Code Implementation (Python) 

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        total = n * (n + 1) // 2
        k = n // m
        divisible_sum = m * (k * (k + 1)) // 2
        non_divisible_sum = total - divisible_sum
        return non_divisible_sum - divisible_sum
Enter fullscreen mode Exit fullscreen mode

⏱️ Time & Space Complexity

  • Time: O(1)
  • Space: O(1)

🧩 Key Takeaways

  • ✅ What concept or trick did I learn?

    • Remembered the formula for the sum of the first n natural numbers and how to apply it to find sums based on divisibility.

  • 💡 What made this problem tricky?

    • It wasn’t immediately obvious that a mathematical approach would be more efficient than brute force.

  • 💭 How will I recognize a similar problem in the future?

    • Look for problems involving sums or sequences where properties of numbers can simplify calculations.

🔁 Reflection (Self-Check)

  • [✅] Could I solve this without help?
  • [✅] Did I write code from scratch?
  • [✅] Did I understand why it works?
  • [✅] Will I be able to recall this in a week?

🚀 Progress Tracker

Metric Value
Day 1
Total Problems Solved 334
Confidence Today 😃
Current Rank 40.25%

Top comments (0)