To Find Number Is Prime Or Not At Very Less Complexity (O(sqrt(n)))

Prime numbers are the numbers which has only 2 factors i.e divisble by 1 and the number itself


Function:

bool isPrime(int n)
{
if(n<=1)   // if number is less than  number is not prime
  return false;
if(n<=2)     // if number is less than 2 than it prime because it is divisible by 2 and 1
  return true;
if(n%2==0||n%3==0)   // if the number is divided by 2 or 3 than it is not prime
{
return false;
}
for(int i=5;i*i<=n;i=i+6) 
     // check for 5 and than 11 than 17 which is all prime number  
   {
    if(n%i==0||n%(i+2)==0) 
   // check for 5 than 7 than 11 than 13 and so on
       return false;
   }
return true;
}

Twisted Prime Number

A Twisted Prime is a number whose itself is a prime number and its reverse is also prime number .


To solve this problem following are the approaches should be taken:

1)Check the number is prime or not 
2) If YES the REVERSE it and check  whether the number is Prime or not.


Programme:

//TO CHECK NUMBER IS PRIME  OR NOT AT   TIMECOMPLEXITYO(SQRT(n))  isPrime()
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)     
           
{
if(n<=1)
  return false;
if(n<=2)
  return true;
if(n%2==0||n%3==0)
{
return false;
}
for(int i=5;i*i<=n;i=i+6)
   {
    if(n%i==0||n%(i+2)==0)
       return false;
   }
return true;
}

int revresee(int n)
{
int sum=0;
while(n>0)
{
int c=n%10;
sum=sum*10+c;
n=n/10;

}
return sum;
}




main()
{
int t;
cin>>t;
while(t>0)
{
int n,c;
cin>>n;
if(isPrime(n))
{
c=revresee(n);
//cout<<c;
if(isPrime(c))
  {
  cout<<"Yes"<<"\n";
  }
  else
    cout<<"No"<<"\n";
}
else
  cout<<"No"<<"\n";
}

}




For PRACTICE this question check this link:
  https://practice.geeksforgeeks.org/problems/twisted-prime-number/0 

Find four elements that sum to a given value

THESE IS THE QUESTION ASKED IN AMAZON AND OYO ROOMS

THE QUESTION IS TO

FIND ALL THE POSSIBLE CASE WHOSE SUM SHOULD BE THE SUM OF FOUR ELEMENTS IN THE ARRAY.

INPUT
 8
 10 2 3 4 5 9 7 8
 23

OUTPUT
  3  5 7 8   (3+5+7+8=23)


For Understanding These Question:

  https://www.geeksforgeeks.org/find-four-numbers-with-sum-equal-to-given-sum/

For Practicing :

 https://practice.geeksforgeeks.org/problems/four-elements/0



PROGRAMME:





#include<bits/stdc++.h>
using namespace std;



void throughnaivesolution(int a[],int n,int X)     //time complexity O(n^4)
{
for(int i=0;i<n-3;i++)
   {
    for(int j=i+1;j<n-2;j++)
    {
    for(int k=j+1;k<n-1;k++)
    {
    for(int l=k+1;l<n;l++)
    {
    if(a[i]+a[j]+a[k]+a[l]==X)
      cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<a[l]<<"\n";
   
    }
    }
    }
   }
}


void throughsorting(int a[],int n,int X)   //O(n^3)
{
sort(a,a+n);
for(int i=0;i<n-3;i++)  //n
{
for(int j=i+1;j<n-2;j++)   //n
{
int k=j+1;
int l=n-1;
while(k<l)     //n
{
if(a[i]+a[j]+a[k]+a[l]==X)
  {
  cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<a[l]<<"\n";
  k++;
  l--;
  }
  else if(a[i]+a[j]+a[k]+a[l]<X)
  {
  k++;
  }
  else
   l--;
}
}
}
}



main()
{
   int t;
   cin>>t;        // NUMBER OF TEST CASES
   while(t--)
   {
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
      cin>>a[i];
   
int X;
cin>>X;

throughnaivesolution(a,n,X);

cout<<"\n\n\n";

throughsorting(a,n,X);
 
     
   
     
     
     
   }
}

Website Recommend

As the placement session comes you want to practice coding challenges or do competitive programming so this are the website recommend for you guys to practice competitive programming .
These are the top website for practicing:

1)HackerEarth
     https://www.hackerearth.com/
2)HackerRank
     https://www.hackerrank.com/
3)CodeChef
          www.codechef.com/
4)GeeksForGeeks
        https://www.geeksforgeeks.org/

Kadane's Algorithm

It is the most asked question in Placements .So,if you are preparing for the placements then you should prepare this algorithm .

Kadane's Algorithm

 This algorithm is used to find the maximium subarray sum in an array . 
  These algorithm is asked many companies : Amazon,Ola,Hike,FactSet,Flipkart .


QUESTION
 
Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.
 
Print the maximum sum of the contiguous sub-array in a separate line for each test case.

INPUT

3

1 2 3

OUTPUT
6
Since maximum sum is(1+2+3) 6.


INPUT
4
-1 -2 -3 -4

OUTPUT
-1   

Since maximum subarray sum is -1

PROBLEM LINK:https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0



Program:

#include<bits/stdc++.h>
using namespace std;

main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
   cin>>a[i];
}

int Max=a[0],sum=a[0];


for(int i=1;i<n;i++)
{


sum=max(a[i],sum+a[i]);


Max=max(Max,sum);
    }

cout<<Max<<"\n";



}


}




OUTPUT SCREEN