Forem: Abdur Rahman Robin

Swap two variables without using third variable (Bitwise XOR)

Abdur Rahman Robin — Sat, 05 Aug 2023 00:34:21 +0000

There are multiple ways of swapping two variables without using third variable in programming. Using Bitwise XOR(^) is one of them. Suppose you have two variables a and b which values are respectively 50 and 100. And if you perform Bitwise XOR operation three times and assign the value respectively to a, b and a - you will find the swapped values which are a = 100 & b = 50.

Things will be more clear if you notice the truth table of Bitwise XOR(^):

X	Y	X ^ Y
0	0	0
0	1	1
1	0	1
1	1	0

Let's do the operations in binary since machine understand only machine code/binary.

a = 50  (base 10) -> 0110010 (base 2)
b = 100 (base 10) -> 1100100 (base 2)

a =  a ^ b
     0110010 
     1100100
-------------
(XOR)1010110

b =  a ^ b
     1010110
     1100100
-------------
(XOR)0110010 [Equivalent to 50(base 10)]

a =  a ^ b
     1010110
     0110010
-------------
(XOR)1100100 [Equivalent to 100(base 10)]

Finally a = 100 and b = 50

To know more about Bitwise XOR, you can visit the official documentation of MDN

Median of Two Sorted Arrays

Abdur Rahman Robin — Sat, 04 Feb 2023 01:35:32 +0000

It's a very easy problem if we ignore the time complexity condition. Merge the two arrays, sort it and return the middle element if the merged array length is odd. And if the merged array length is even, add two middle elements and divide it by 2 and return the result.

But we should maintain the logarithmic time complexity, e.g: O(log(m+n))

So we should use any algorithm or technique that gives us logarithmic time complexity. And that is none other than Binary Search!

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let [a, b] = [nums1, nums2]
    const total = nums1.length + nums2.length
    const half = Math.floor(total/2) 

    if (a.length > b.length) {
        [a, b] = [nums2, nums1] 
        // we always do binary search in the smaller array which gives us time complexity O(log(min(m, n)))
    }

    let [left, right] = [0, a.length - 1]

    while(true) {
        let middleOfA = Math.floor((left + right) / 2)
        let middleOfB = half - middleOfA - 2 

        /*
        In left partition, if middle value is not found - that means middle index is less than 0(zero).
        That's why we are using -Infinity in this case.
        And vice-versa in the right partition.
        */
        let aLeft = a[middleOfA] !== undefined ? a[middleOfA] : -Infinity
        let aRight = a[middleOfA + 1] !== undefined ? a[middleOfA + 1] : Infinity
        let bLeft = b[middleOfB] !== undefined ? b[middleOfB] : -Infinity
        let bRight = b[middleOfB + 1] !== undefined ? b[middleOfB + 1] : Infinity

        if (aLeft <= bRight && bLeft <= aRight) {
            // that means our partition is correct
            if (total % 2 !== 0) return Math.min(aRight, bRight)
            else return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2 || 0.00
        } else if (aLeft > bRight) {
            // so we need to reduce the size of aLeft
            right = middleOfA - 1
        }else { 
            // bLeft > aRight, increase the size of aLeft
            left = middleOfA + 1
        }
    }
};

What does the Array method `reduce` do?

Abdur Rahman Robin — Mon, 07 Mar 2022 04:26:50 +0000

First of all, the name "reduce" doesn't actually reduce anything. It's a confusional/tricky naming convention you often find in programming. Although for better understanding you can assume - it takes lots of values and reduce them into a single value and return.

reduce is a higher order function which takes two arguments:

Callback function and
Initial Value.

And the callback function takes four arguments:

previousValue,
currentValue,
currentIndex,
array

More often you will find the callback function takes only two arguments according to the problem we need to solve, which is Okay.

[1, 2, 3].reduce((previousValue, currentValue, currentIndex, array) => {
  // here the return statement goes...
}, initialValue);

Now let's look at a practical example. Write a program to return the sum of all the elements in an array. Please think in a as-usual way/procedure first, then we will solve the same thing with reduce. Here is the as-usual way/procedure of writing this program:

function sum(arr) {
  let sum = 0;
  for(let i = 0; i < array.length; i++) {
    sum = sum + arr[i];
  }
  return sum;
}

So, if we call sum with an array it will return the sum of it's all elements. Right?

Yeah, And we can do the same thing with reduce also. Here is the code:

[1, 2, 3, 4].reduce(function(previousValue, currentValue) {
  let result = previousValue + currentValue;
  return result;
}, 0);

It does the same thing. The reducer walks through the array element, at each step adding the current array value to the result from the previous step (this result is the running sum of all the previous steps) - until there are no more elements to add.(reference: here)

Here the previousValue is the as-usual sum and currentValue is the as-usual arr[i].

In the first iteration, there is no previousValue (return value of the previous calculation) - right? In this case, initialValue will be used as previousValue. If there is no initialValue, the array element at index 0 is used as the initial value and iteration starts from the next element (index 1 instead of index 0).

Instead of using extra variable result, you can write the program like this:

[1, 2, 3, 4].reduce(function(previousValue, currentValue) {
  previousValue += currentValue;
  return previousValue;
}, 0);

And more shortly:

[1, 2, 3, 4].reduce((previousValue, currentValue) => previousValue += currentValue, 0);

Hope you understand. Now it's your task to write a program which will find the minimum number from a non-empty array using reduce (consider all the elements in the array are positive).

Here it is:

const arr = [4, 2, 3, 1];
let result = arr.reduce((minValue, currentValue) => {
  if (currentValue < minValue) {
    minValue = currentValue;
  }
  return minValue;
}); // no initial value 😎
console.log(result);

❤️ Happy Coding ❤️