Introduction to competitive programming

Problem :

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
 
	public:
    	bool isHappy(int n) 
	{
		map<int,int>a;
		while(a[n]!=1)
		{
			a[n]=1;
        		int sum=0,res=0;
			while(n)
			{
				res=n%10;
				sum+=(res*res);
				n/=10;
			}
			if(sum==1)
			return true;
			else
			{
				n=sum;
			}
		}
		return false;
    	}
};
int main()
{
	Solution s;	
	cout<<s.isHappy(19)<<endl;
	cout<<s.isHappy(301)<<endl;
}

Problem:

Link

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
    public:
    bool isPalindrome(int x) 
    {
        if(x<0)
 return false;
 stringstream ss;
 ss<<x;
 string s1="",s,temp;
 s=ss.str();
 for(int i=0;i<s.length();i++)
 {
  if(s[i]!=' ')
  s1+=s[i];
 }
 temp=s1;
 reverse(s1.begin(),s1.end());
 return s1==temp?true:false;
    }
};
int main()
{
 Solution s;
 cout<<s.isPalindrome(131)<<endl;
 cout<<s.isPalindrome(-456)<<endl;
}

Problem:

Link

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
	public:
  	int titleToNumber(string s) 
	{
        	int n=s.length(),ans=0;
		for(int i=0;i<n;i++)
		{
			ans+=(pow(26,n-i-1))*(s[i]-'A'+1);
 
		}
		return ans;
    	}
};

Problem:

Reference : http://www.mytechinterviews.com/how-many-trailing-zeros-in-100-factorial

#include<iostream>
using namespace std;
class Solution 
{
public:
      int trailingZeroes(int n) {
        int count = 0;
        long k = 5;
        while(n >= k)
        {
            count+=n/k;
            k*=5;
        }
        return count;
    }
};
int main()
{
	Solution s;
	cout<<s.trailingZeroes(100)<<endl;
}

Problem:

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
 public:
     int reverse(int x) 
 { 
  int res=0,ans=0,f=0;
  while(x)
  {
   if(ans>(INT_MAX/10) || ans<(INT_MIN/10))
   return 0;
   ans=ans*10+x%10;
   x/=10;
 
  }
 
  return ans;
 
   }
};

Problem:

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
	public:
    	vector<int> spiralOrder(vector<vector<int> > &matrix) 
	{
		vector<int>v;
		if(matrix.size()==0)
		return v;
 
        	int t=0,b=matrix.size()-1,l=0,r=matrix[0].size()-1;
		while(1)
		{
			for(int i=t;i<=r;i++)
			v.push_back(matrix[t][i]);t++;
			if(l>r || t>b) break;
			for(int i=t;i<=b;i++)
			v.push_back(matrix[i][r]);r--;
			if(l>r || t>b) break;
			for(int i=r;i>=l;i--)
			v.push_back(matrix[b][i]);b--;
			if(l>r || t>b) break;
			for(int i=b;i>=t;i--)
			v.push_back(matrix[i][l]);l++;
			if(l>r || t>b) break;
 
 
 
		}
	return v;
    	}
};

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;
}

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;
    }
};