Day #1/50 of Learning DSA

Today, I started with little but of theory followed by video lectures to revise the concepts. Solved around 5 programming question, really essential to recall (revise) programming concepts quickly.

Key Concepts Revised:
\> Data types (int, long, char, float, bool & double)
\> Type Casting (implicit & explicit)
\> Binary Operators (Arithmetic, relational & logical)
\> Unary Operators (Increment & Decrement)
\> Conditional Statements (if-else, ternary statements, switch-case)
\> Loops (while, for, do-while)
\> Binary Number System (D to B, B to D)

#Leap Year: Only things to remember for finding whether the given year is leap year or not.

Explanation:
1. If the year is divisible by 400, then it is a leap year. (This condition checks for century leap years)
2. If the year is divisible by 4 but not by 100, then it is a leap year. (This condition eliminates century years which are not a leap year, still considering non century leap years)
3. In any other case it is not a leap year.

    bool checkYear(int n) {
        if (n%400 == 0){
            return true;
        } else if(n%4 == 0 && n%100 != 0){
            return true;
        } else {
            return false;
        }
    }

#Add Digits: Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

1. Brute force approach: Explanation
\> Get the digits of number.
\> Find the sum of digits.
\> Check if the sum is in single digit or not (if not reiterate the loop).
\> Return the single digit sum (num).

   int addDigits(int num) {
        while(num > 9){
            int sum = 0;
            while(num != 0){
                int digit = num % 10;
                num /= 10;
                sum += digit;
            }
            num = sum;
        }
        return num;
    }

#Reverse Integer: Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2<sup>31</sup>, 2<sup>31</sup> - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
\> Get the digits.
\> Store the digits in reversed order in a new variable.
\> Check if the ans (reversed integer) is within the limits of a signed integer.
\> Return 0 (if any overflow condition is reached)
\> Return reversed number (if the number reversed in inside INT limits).

    int reverse(int x) {
        int ans = 0;
        while(x!=0){
            int digit = x % 10;
            x /= 10;
            if(ans > INT_MAX/10 || ans < INT_MIN/10){
                return 0;
            } else {
                ans = ans * 10 + digit;
            }
        }
        return ans;
    }

#Power of Two: Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two, if there exists an integer x such that n == 2<sup>x</sup>.

Approach 1: Keep comparing the number with power of two iteratively, while number is greater than & equal to power of two.

    bool isPowerOfTwo(int n) {
        if (n < 1) return false;
        long int powOfTwo = 1; // 2^0
        while (n >= powOfTwo){
            if (n == powOfTwo ){
                return true;
            }
            powOfTwo *= 2;
        }
        return false;
    }

Approach 2: Keep checking the remainder of the number with modulo 2 & keep dividing the number by 2. If the remainder is not equal to 1, then the given number is power of two.

    bool isPowerOfTwo(int n) {
        if (n < 1) return false;

        while (n!=1){
            if (n%2 == 1) return false;

            n /= 2;
        }
        return true;
    }

#Sqrt(x): Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
Note: You must not use any built-in exponent function or operator.

    int mySqrt(int x) {
        long long square = 1;
        int squareRoot = 1;
        while (x > square){
            squareRoot++;
            square = 1LL * squareRoot * squareRoot;
        }
        if (x == square){
            return squareRoot;
        }
        return squareRoot-1;
    }

In conclusion, understanding fundamental programming problems such as determining leap years, adding digits, reversing integers, checking for powers of two, and calculating square roots is essential for developing problem-solving skills. These exercises not only enhance logical thinking but also provide a solid foundation for tackling more complex computational challenges. By mastering these concepts, one can improve their coding proficiency and apply these techniques to a wide range of real-world applications.