Introduction to competitive programming

Problem:

My brute force solutions get accepted,the algorithm is to push all the remainders into a stack and then multiplying each bit with corresponding power of 2

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
 int reverseBits(int n) 
 {
         int x=1,i=0;
  long long res=0;
  stack<int>st;
  while(x<=32)
  {
   st.push(abs(n%2));
   n>>=1;
   x++;
  }
  res=0;
  while(!st.empty())
  { 
   res+=(st.top()*(pow(2,i)));
   i++;
   st.pop();
  }
  return res;
   }
};

Reference :

Method 2

#include<bits/stdc++.h>
#define INT_SIZE 32
using namespace std;
class Solution 
{
 public:
 int reverseBits(unsigned int num)
 {
  int i=INT_SIZE-1;
  unsigned int rev_num=0;
  while(i>=0 && num)
  {
   if(num & 1)
   rev_num |= (1<<i);
   num>>=1;
   i--;
  }
 return rev_num;
 }
};
int main()
{
 Solution s;
 cout<<s.reverseBits(8)<<endl;
}

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
This algorithm needs to sort edges in non-decreasing order and uses a disjoint-set data structure to keep track which vertex is in which component.

Algorithm:Kruskal

MST-KRUSKAL(G,w)
1  A = φ
2. for each vertex 2 ∈ G:V
3. Make_set{}
4. Sort the edges in non-decreasing order by weight
5. for each edge(u,v) ∈ G,E is taken from non-decreasing order by weight
6. if(find_set(u)!=find_set(v)
7. A=A U {(u,v)}
8. Union(u,v)
9. return A

Here is the C++ implementation of Kruskal algorithm

#include<bits/stdc++.h>
using namespace std;
#define MAX 100
#define edge pair< int,int >
vector< pair<int,edge> >G,MST;
int parent[MAX];
void reset(int n)
{
 G.clear();
 MST.clear();
 for(int i=0;i<=n;i++)
 parent[i]=i;
 
}
int find(int x)
{
 if(x!=parent[x])
 parent[x]=find(parent[x]);
 return parent[x];
}
int main()
{
 int n,e,u,v,w,pu,pv,total=0;
 cin>>n>>e;
 reset(n);
 for(int i=0;i<e;i++)
 {
  cin>>u>>v>>w;
  G.push_back(pair<int,edge >(w,make_pair(u,v)));// w(u,v) format
 }
 sort(G.begin(),G.end());    //sort will be done in increasing order of weight
 for(int i=0;i<e;i++)
 {
  pu=find(G[i].second.first); 
  pv=find(G[i].second.second);
  if((pu)!=(pv))
  {
   MST.push_back(G[i]);
   total+=G[i].first;
   parent[pu]=parent[pv];
  }
 }
 for(int i=0;i<MST.size();i++)
 {
  cout<<"("<<MST[i].second.first<<" "<<MST[i].second.second<<" ) :"<<MST[i].first<<endl;
 }
 cout<<"Mimimum cost for spanning tree is :"<<total<<endl;
}

Problem:

class Solution {
public:
    bool isPalindrome(string s) {
        int n=s.length(),f=1;
 string temp="";
 for(int i=0;i<n;i++) 
 {
  if(isalpha(s[i])||isdigit(s[i]))
  temp+=tolower(s[i]);
 }
 int len=temp.length();
 for(int i=0;i<len/2;i++) 
 {
  if(temp[i]!=temp[len-i-1])
  {
   return false;
  }
 }
 return true;
    }
};

Problem:

Just find the power of Last disit using Logarithmic exponentiation

Here is the C++ implementation

#include<stdio.h>
long long modexpo(long long a,long long b,long long n)
{
    long long d=1;
    while(b)
    {
        if(b%2)
            d=(d*a)%n;
        b>>=1;
        a=(a*a)%n;
    }
    return d;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long a,b;
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",modexpo(a,b,10));
    }
    return 0;
}

Problem:

The problem is about re-ordering the given trucks in an increasing order by using a temporary street.We can solve it by using stack

Here is the C++ implementation

#include<cstdio>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int main()
{
    long long n;
     cin>>n;
     while(n)
    {
        long long ans=1;
 
        long long a[n+10];
        for(long long i=1;i<=n;i++)
            cin>>a[i];
        stack<long long>st;
        long long strt=1;
        for(long long i=1;i<=n;i++)
        {
            if(a[i]==strt)
                strt++;
            else
            {
                if(st.empty())
                {
                      st.push(a[i]);
 
                }
 
                else if(!st.empty() && st.top()<a[i])
                {
 
                    ans=0;
                    break;
                }
                else
                    st.push(a[i]);
            }
 
            while(!st.empty() && st.top()==strt)
            {
                st.pop();
                strt++;
            }
        }
        if(!ans)
            printf("no\n");
        else if(strt-1==n && st.empty())
            printf("yes\n");
            cin>>n;
    }
}