Day 1

I started a day with Problem of the day in GeeksforGeeks. The coding question was named "Remove K Digits". it is a stack problem.

Problem statement:

Given a non-negative integer S represented as a string, remove K digits from the number so that the new number is the smallest possible.
Note : The given num does not contain any leading zero.

SAMPLE

Input:
S = "149811", K = 3
Output: 
111
Explanation: 
Remove the three digits 
4, 9, and 8 to form the new number 111
which is smallest.

Problem Explanation and problem Approach

S is the string containing a number and we have to remove K digits from the S such that the remaining numbers can form a smallest number possible.

I used stack to solve this problem, traverse complete string using a for loop.... Inside for loop we have a while loop whose condition is stack should not be empty , the top element of stack should be greater than index and k should be greater than zero.

inside while loop we remove the top element of stack and reduce the k by 1. Outside while loop we push element in the stack.

End of for loop we have to check if we have removed k or not if not we pop the top elements and finally we would have remove k elements. so now start while loop and save the remaining in a string. After end of while loop we will have a reverse string, I used reverse builtin function to reverse the string.

This is not the end of the solution we forgot a case where there is a leading zeros and we need to remove those zeros, for that we start traversing from that index 0 and keep on moving ahead until we get a char which is not '0' and we return a sub string from that index using substr builtin function.

CODE

string removeKdigits(string S, int k) {
  if(k>S.size()) //border case
      return "0";
  stack<char>st;
  for(int i=0;i<S.size();i++)
  {
      while(!st.empty() && st.top()>S[i] && k>0){ //if top ele is greater then ele
         st.pop();
         k--;
      }
      st.push(S[i]);
  }
  if(st.empty()) //if st is empty then return 0;
       return "0";
  while(k--) //if k is still not 0 then remove remaining elements.
    st.pop();
    string res; // storing the stack ele in string.
    while(!st.empty()){
      res.push_back(st.top());
      st.pop();
    }
    reverse(res.begin(),res.end());
    int i=0;
    while(res[i]=='0') //remove leading zeros
      i++;
    if(i==res.size())
      return "0";
    return res.substr(i);   //here it returns from ith index to the end of string.
    }

Next question

Problem statement: Given an integer N and an integer D, rotate the binary representation of the integer N by D digits to the left as well as right and return the results in their decimal representation after each of the rotation.
Note: Integer N is stored using 16 bits. i.e. 12 will be stored as 0000000000001100.

Input:
N = 28, D = 2
Output:
112
7
Explanation: 
28 in Binary is: 0000000000011100
Rotating left by 2 positions, it becomes 0000000001110000 = 112 (in decimal).
Rotating right by 2 positions, it becomes 0000000000000111 = 7 (in decimal).

we are given 2 integers n and d where we have to convert n into binary representation and shift the bits left and right by d places. finally we have to return a vector containing decimal value of left and right rotated bits. For this we are taking bits of size 16 as we are considering bits of 16 places(given in question) and 2 variables to store left rotated value and right rotated value.

To convert number N to decimal to bits we use for loop from index 0 to 16 then in each array slot we will have 0 or 1 by taking n%2 and then divide n by 2 .

we will take another variable sum, then we start a for loop where initial value of i is (16-d) because after shifting elements by d times the first element in 2^0 position is (16-d)%16 and j starts from 0 till 16. inside the loop we check if bits[i] is equal to 1 if it's true add sum to the left, where sum is the decimal converted part of a binary represented digit.

similarly we do it for the right shift also, then push it to the vector and return the vector.

vector <int> rotate (int n, int d)
        {
            int left=0,right=0,bits[16];
            int i,j;
            d=d%16;
            for(i=0;i<16;i++) //converting decimal to binary
            {
                bits[i]=n%2;
                n=n/2;
            }
            int sum=1;
            for(i=(16-d)%16,j=0;j<16;j++,i=(i+1)%16) 
            { //when shifting left the first ele(2^0 ele) is (16-d)%16
                if(bits[i]==1)
                {
                    left=left+sum;
                }
                sum=sum*2;
            }
            sum=1;
            for(i=d,j=0;j<16;j++,i=(i+1)%16)
            {//when shifting right the first ele(2^0 ele) is d
                if(bits[i]==1)
                    right=right+sum;
                sum=sum*2;
            }
            vector<int>ans;
            ans.push_back(left);
            ans.push_back(right);
            return ans;
        }

Today while browsing Youtube I came across Dynamic programming by Aditya verma and I want to start learning through it. I want to complete the playlist in a month. Is it possible?? lets see.....

For the Outdoor activity I walked for 30 mins. yeah I know it's less but wanted to start slow.