📅Day-6 Striver’s SDE Sheet | Arrays Part 2 Find the Repeating and Missing Number , Count inversions in an array

Note : Started my 27-day DSA journey with Striver’s SDE Sheet!
I will be journaling every day — recording what I learn, reflecting on it, and sharing it with my network to help fellow learners and aspiring developers.. Learning through videos, resources, and the internet — simplifying logic in my own way with real-world connections. Sharing 2 questions daily: brute-force to optimal, clean Java code, time & space complexity, and key patterns.

This blog series is for anyone preparing for coding interviews — whether you’re a beginner or a revision warrior. Let’s grow together! 🚀

Namaste Developers! 🙏

Welcome to Day 6 of my 27-day DSA journey using Striver’s SDE Sheet!

1️⃣Find the repeating and missing numbers

🔸 Problem Statement:

Given an integer array nums of size n containing values from [1, n] and each value appears exactly once in the array, except for A, which appears twice and B which is missing.

Return the values A and B, as an array of size 2, where A appears in the 0-th index and B in the 1st index.

Note: You are not allowed to modify the original array.

Examples:
Input: nums = [3, 5, 4, 1, 1]

Output: [1, 2]

Explanation: 1 appears two times in the array and 2 is missing from nums

Input: nums = [1, 2, 3, 6, 7, 5, 7]

Output: [7, 4]

Explanation: 7 appears two times in the array and 4 is missing from nums.

Constraints:

• n == nums.length

• 1 <= n <= 10⁵

• n - 2 elements in nums appear exactly once and are valued between [1, n].

• 1 element in nums appears twice, and is valued between [1, n].

💠Real-Life Example:

Imagine you're a teacher checking exam roll numbers.
You expect each student to have a unique roll number from 1 to n.
But by mistake:

• One student used another’s roll number

• One student missed writing theirs

Now your task is to find:

• Who repeated?

• Who is missing?

📌 And no—you can’t mark on the attendance sheet (you can't modify the array)!

📍Brute Force Approach

➡️ Idea:

Check each number from 1 to n:

• Count how many times it appears in the array

• If frequency is 2 → that’s duplicate

If frequency is 0 → that’s missing

class Solution {
    public int[] findMissingRepeatingNumbers(int[] nums) {
        int n = nums.length;
        int[] freq = new int[n + 1];

        // Count frequencies
        for (int num : nums) {
            freq[num]++;
        }

        int repeating = -1, missing = -1;
        // Find which number appears twice and which is missing
        for (int i = 1; i <= n; i++) {
            if (freq[i] == 2) {
                repeating = i;
            } else if (freq[i] == 0) {
                missing = i;
            }
        }

        return new int[]{repeating, missing};
    }
}

📍Time Complexity: O(n)

📍Space Complexity: O(n)

(Extra array used)

👎 Not allowed in interviews where extra space is restricted.

💠Optimal Approach – Using Math (Without Modifying Array)

\=> Smart Trick using Sum and Sum of Squares

Concept:

Let:

• S = Sum of first n natural numbers = n(n+1)/2

• S2 = Sum of squares of first n natural numbers = n(n+1)(2n+1)/6

Let x be the missing number and y be the repeating number.

From given array:

• Let actualSum = sum of nums

• Let actualSqSum = sum of squares of nums

Then:

Equation 1: actualSum = S - x + y  ⇒  (y - x) = actualSum - S  
Equation 2: actualSqSum = S2 - x² + y²  ⇒ (y² - x²) = actualSqSum - S2

Now:

• y - x = diff1

• y² - x² = (y - x)(y + x) = diff2
  ⇒ Solve these two equations to find x and y

class Solution {
    public int[] findMissingRepeatingNumbers(int[] nums) {
        int n = nums.length;
        long S = (long) n * (n + 1) / 2;
        long S2 = (long) n * (n + 1) * (2L * n + 1) / 6;

        long actualSum = 0;
        long actualSqSum = 0;
        for (int num : nums) {
            actualSum += num;
            actualSqSum += (long) num * num;
        }

        long diff1 = actualSum - S;       // y − x
        long diff2 = actualSqSum - S2;    // y² − x²

        long sumYX = diff2 / diff1;       // (y + x)

        long y = (diff1 + sumYX) / 2;     // repeating number
        long x = sumYX - y;               // missing number

        return new int[]{(int) y, (int) x};
    }
}

📍Time Complexity:

• O(n) ✅

📍 Space Complexity:

• O(1) ✅
  (No extra space, just variables)

💠(Hinglish:

• Math lagao, array mat chhedo – use sum and sum of squares

• Do equations banao – y - x and y² - x²

• Divide & conquer se solve karo

• Space bilkul nahi lena hai – use variables only

• Fast and clean solution – interviewer ko pasand aayega ✅)

💠Bonus – Why at least one duplicate and missing exists?

Because:

• You have numbers in [1, n]

• But one number repeats → Someone must be missing

• It's like saying: "Ek seat pe do baithe, toh ek seat khali reh gayi!"

💠Final Thoughts:

This problem is a perfect example of using math to optimize space.
Instead of searching element-by-element, we used sum tricks to calculate the answer with clean logic.

📌 Kabhi kabhi soch seedhi nahi hoti – lekin smart hoti hai

---

2️⃣Count inversions in an array

🔸 Problem Statement:

Given an array of N integers, count the inversion of the array (using merge-sort).

What is an inversion of an array? Definition: for all i & j < size of array, if i < j then you have to find pair (A[i],A[j]) such that A[j] < A[i].

Example 1:
Input Format: N = 5, array[] = {1,2,3,4,5}
Result: 0
Explanation: we have a sorted array and the sorted array has 0 inversions as for i < j you will never find a pair such that A[j] < A[i]. More clear example: 2 has index 1 and 5 has index 4 now 1 < 5 but 2 < 5 so this is not an inversion.

Example 2:
Input Format: N = 5, array[] = {5,4,3,2,1}
Result: 10
Explanation: we have a reverse sorted array and we will get the maximum inversions as for i < j we will always find a pair such that A[j] < A[i]. Example: 5 has index 0 and 3 has index 2 now (5,3) pair is inversion as 0 < 2 and 5 > 3 which will satisfy out conditions and for reverse sorted array we will get maximum inversions and that is (n)*(n-1) / 2.For above given array there is 4 + 3 + 2 + 1 = 10 inversions.

Example 3:
Input Format: N = 5, array[] = {5,3,2,1,4}
Result: 7
Explanation: There are 7 pairs (5,1), (5,3), (5,2), (5,4),(3,2), (3,1), (2,1) and we have left 2 pairs (2,4) and (1,4) as both are not satisfy our condition.

📍 Real-Life Example:

Imagine a queue of students standing in height order for a class photo. Normally, shorter students should stand in front (sorted order).
If a taller student stands in front of a shorter one, that's "inversion" in our lineup!

In DSA, that’s exactly what we call an inversion in an array.

📍Trick to Remember:

"Whenever a bigger number comes before a smaller one, inversion mil gaya bhai!"

💠 Brute Force Approach:

Logic:

• Run 2 nested loops (i and j)

• Check every pair (i, j) where i < j

• Count if arr[i] > arr[j]

class Solution {
    public long numberOfInversions(int[] nums) {
        int n = nums.length;
        long count = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

📍Time Complexity: O(N²)

📍 Space Complexity: O(1)

❌ Not suitable for large arrays!

💠Optimal Approach – Using Modified Merge Sort

📍 Idea

While merging two sorted halves, if any element from right half is smaller than from left, then all elements from left[i] to mid are greater than right[j] – so count them as inversions.

📍Dry Run Kar Ke Samjho:

Let’s say we are merging two sorted subarrays:
Left: [2, 5] and Right: [1, 3]
While comparing 2 & 1 → 2 > 1 → means 2 and 5 are greater than 1 → count += 2

public class Solution {
    public long numberOfInversions(int[] nums) {
        return mergeSortCount(nums, 0, nums.length - 1);
    }

    private long mergeSortCount(int[] arr, int low, int high) {
        long cnt = 0;
        if (low < high) {
            int mid = (low + high) / 2;
            cnt += mergeSortCount(arr, low, mid);
            cnt += mergeSortCount(arr, mid + 1, high);
            cnt += merge(arr, low, mid, high);
        }
        return cnt;
    }

    private long merge(int[] arr, int low, int mid, int high) {
        List<Integer> temp = new ArrayList<>();
        int left = low, right = mid + 1;
        long cnt = 0;
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp.add(arr[left++]);
            } else {
                temp.add(arr[right++]);
                cnt += (mid - left + 1);
            }
        }
        while (left <= mid) temp.add(arr[left++]);
        while (right <= high) temp.add(arr[right++]);
        for (int i = low; i <= high; i++) arr[i] = temp.get(i - low);
        return cnt;
    }
}

📍Time Complexity: O(N log N)

📍 Space Complexity: O(1)

✅ Efficient even for large arrays. Merge Sort is

💠(Hinglish :

• Inversion ka matlab hai – jab koi bada number pehle ho aur chhota baad mein ho (i < j but arr[i] > arr[j])

• Brute force chalega small inputs ke liye, but large inputs me timeout milega

• Merge sort ko modify karke hum inversions count kar sakte hai during merge phase – bina extra loop ke

• Time Complexity O(N log N) = sorted array jaisa fast, easy to apply in interviews)

📌 Final Takeaway:

If you're given a problem to count inversion in an array:

• Brute force = simple, but slow

• Merge sort = fast and optimal

"Inversions count batata hai kitna unordered hai array — jaise school line me sab height wise khade nahi hue ho "

✍️ Final Notes:

If you're just starting your DSA journey like me, don't worry if you don’t get it perfect the first time.
Visualize → Dry Run → Optimize.
Stay consistent, and let’s crack every problem from brute to optimal! 💪

🙏 Special Thanks

A heartfelt thank you to Rajvikraaditya Sir for creating and sharing such an incredible DSA resource with the community (takeuforward). Your structured approach has made DSA more accessible and less intimidating for thousands of learners like me.

If this helped you, do share it with your fellow DSA learners.
Comment with your doubts — I’d love to answer and grow together 🌱

✍️ Payal Kumari 👩‍💻
My 27-Day DSA Journey with Striver’s Sheet! #dsawithpayal