Day #2/50 of Learning DSA

Today, I focused on solving a series of intriguing programming challenges that reinforced my understanding of key concepts. These problems included finding the complement of a base 10 integer, determining if a number is a palindrome, checking if an array is sorted, and identifying the second largest element in an array. Each problem provided a unique opportunity to apply and deepen my knowledge of algorithms and data structures.

Complement of Base 10 Integer:

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.
For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.
Given an integer n, return its complement.

Approach:

• Convert the decimal into binary & reverse the bits (complement) using XOR (^) or (!).

• Reconvert the binary complement into decimal by multiplying each bit with increasing power of 2.

    int bitwiseComplement(int n) {
        if (n==0) return 1;

        int ans = 0;
        long powOfTwo = 1; // 2^0
        while(n != 0){
            int rem = n % 2;
            n /= 2;
            ans = ans + !rem * powOfTwo;
            powOfTwo *= 2;
        }
        return ans;
    }

Palindrome Number:

Given an integer x, return true if x is a palindrome*, and* false otherwise.

Approach:

• Take a copy & reverse the given number.

• Check if the reversed number is same as original number.

    bool isPalindrome(int x) {
        if (x < 0) return false;

        int original = x;
        long reversed = 0;
        while(x>0){
            int digit = x % 10;
            reversed = reversed * 10 + digit;
            x = x/10;
        }
        return original == reversed;
    }

Check if array is sorted:

Given an array arr[], check whether it is sorted in non-decreasing order. Return true if it is sorted otherwise false.

Approach:

• Keep checking the current element with the next number, such that arr[i]<=arr[i+1] this condition is satisfied through out the array elements;

• Return false if the condition fails.

• Return true if everything goes well.

    bool isSorted(vector<int>& nums) {
        for(int i=0; i<nums.size()-1; i++){
                if(!(nums[i]<=nums[i+1])){
                    return false;
                }
        }
        return true;
    }

Second Largest:

Given an array of positive integers arr[], return the second largest element from the array. If the second largest element doesn't exist then return -1.
Note: The second largest element should not be equal to the largest element.

1. Brute Force Approach:

• Sort the array in non-decreasing order.

• Take the (last) largest element and compare it with 2nd last and following in reverse order.

• The first available smaller element in the array is the 2nd largest element in the array.

    int getSecondLargest(vector<int> &arr) {
        int n = arr.size();
        sort(arr.begin(), arr.end());

        for(int i=n-2; i>=0; i--){
            if(arr[i]<arr[n-1]){
                return arr[i];
            }
        }
        return -1;

    }

2. Better Approach:

• Pass 1: Get the largest element in the 1st pass.

• Pass 2: Get the 2nd largest element in the 2nd pass by comparing with largest element.

    int getSecondLargest(vector<int> &arr) {
        int n = arr.size();

        int largest = arr[0];
        for (int i=1; i<n; i++){
            if (arr[i]>largest){
                largest = arr[i];
            }
        }

        int secondLargest = -1;
        for (int i=0; i<n; i++){
            if(arr[i]>secondLargest && arr[i]<largest){
                secondLargest = arr[i];
            }
        }
        return secondLargest;
    }

3. Optimal Approach:

• Check for the largest element in the array and simultaneously update the 2nd largest element when new largest element is found.

• Also, update the 2nd largest if element larger then 2nd largest but smaller than largest is found.

    int getSecondLargest(vector<int> &arr) {
        int n = arr.size();
        int largest = arr[0];
        int secondLargest = -1; 
        //secondLargest = INT_MIN; (if considering -ve elements)

        for (int i=0; i<n; i++){
            if (arr[i]>largest){
                secondLargest = largest;
                largest = arr[i];
            } else if (arr[i]<largest && arr[i]>secondLargest){
                secondLargest = arr[i];
            }
        }
        return secondLargest; 
        //return secondLargest == INT_MIN ? -1 : secondLargest;

    }