Miller Rabin Primality Test
leave a comment »

Miller Rabin Primality Test is a probabilistic test to check whether a number is a prime or not. It relies on an equality or set of equalities that hold true for prime values, then checks whether or not they hold for a number that we want to test for primality.

Theory

1> Fermat’s little theorem states that if p is a prime and 1 ≤ a < p then
2> If p is a prime and or then or
3> If n is an odd prime then n-1 is an even number and can be written as . By Fermat’s Little Theorem either or for some 1 ≤ r ≤  s-1.
4> The Miller–Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an a such that and for all 1 ≤ r ≤  s-1 then a is witness of compositeness of n and we can say n is not a prime. Otherwise, n may be a prime.
5> We test our number N for some random a and either declare that N is definitely a composite or probably a prime. The probably that a composite number is returned as prime after k itereations is

WAP to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order.

For Ex : in the circular array ABCDEABCCDE
The answer is 6 because the circular string starting from the element A in the 6th position comes first in the dictionary formed from all the possible strings of the circular array

what is lexicographic order
Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as
(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).

so basically we have to print 1st index from differentstring formed by same character leads different lexicographic order such that string comes 1st then other string in lexicographic order from all others .Some of you may stuck with language i written but example makes you more clear

so in case of Given string s= ABCDEABCCDEA
A comes at 0,5 & 11th position as you can see AA comes 1st then ABCCDE in lexicographic order or alphabetically order or dictionary order then ABCDE so output will be 11 not 0 or 5th index . you can easily visualize it you know about TRIE or Dictionary

This problem can be Solved in Two Ways

1st Simple Iterative Solution

#include
#include


int findIndex(const char* str){

int minindex= 0, i, j, k, temp, len = strlen(str);

for(i = 1; i < len; ++i){

if(str[i] < str[ret]){

minindex= i;

} else if(str[i] == str[ret]){

k = i;
temp= ret;

for(j = 0 ; j < len; j++){

k = (k + j) % len;
temp= (temp + j) % len;

if(str[k] < str[l]){
minindex = i;
break;//once we found minindex terminate to optimize the inner loop
}
}
}
}
return ret;
}
int main() {

char *s = "ABCDEABCCDEA";

printf("%d\n", findIndex(s));
}

Time Complexity O(N^2) when suppose ABCDEFGHACDEFGHA so only inner loop will run until last index of A. isn't it i suggest you to dry run it.
Space Complexity O(1)
Run Here http://ideone.com/rgMSE

2nd DP Solution

PS:Working On The Code ..

WAP to Print Disjoint Set with Associated Property In Set

Given a set of overlapping intervals of the form (start, end), each of which is associated with a property (say S), print a sequence of disjoint intervals with all properties current valid in that interval. eg. (1, 3, S0) (2, 3, S1) (2, 4, S2) yields (1,2, S0), (2, 3, S0 + S1 + S2), (3,4,S2) as the disjoint intervals.Also, code a solution to the above problem.

Algorithm

1. make a list from all mins and maxes from the given intervals
2. sort the list and remove duplicates from the list by making it set (as no duplicate)
3. construct intervals from every two consecutive numbers from the list and check
whether this interval is included by the original set of intervals or not
if yes then keep adding interval with associated property else
else create new interval & repeat until we are out of set

Data Structure used: Set,HashSet,ArrayList,Array

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;

class Interval {

class Set {
Integer maximum;
Integer minimum;
String attribute;

Set(Integer minimum, Integer maximum, String attribute) {
this.minimum = minimum;
this.maximum = maximum;
this.attribute = attribute;
}
}

private void getInterval(HashSet uniqueList, Set [] intervals) {
int start =0, end = 0;
ArrayList output = new ArrayList ();
Iterator iterator = uniqueList.iterator();
start =-1;
while(iterator.hasNext()) {
end = iterator.next();
Set temp = new Set(start, end, " ");
for(int i=0;i if(temp.minimum >= intervals[i].minimum &&
temp.maximum <= intervals[i].maximum) {
if(temp.attribute.equals(" ")) {
temp.attribute = intervals[i].attribute;
} else {
temp.attribute += ", " + intervals[i].attribute;
}
}
else if(intervals[i].minimum > end) {
break;
}
}
if(!temp.attribute.equals(" "))
output.add(temp);
start = end;
}
for(int i=0;i Set temp = output.get(i);
System.out.println("( " + temp.minimum + " " + temp.maximum +
" " + temp.attribute + " )" );
}
}

public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Set [] intervals = new Set[n];
Interval interval = new Interval();
for(int i=0;i intervals [i]= interval.new Set(Integer.parseInt(br.readLine()),
Integer.parseInt(br.readLine()), br.readLine());
ArrayList list = new ArrayList();
for(int i=0;i list.add(intervals[i].minimum);
list.add(intervals[i].maximum);
}
Collections.sort(list);
HashSet uniqueList = new HashSet(list);
interval.getInterval(uniqueList, intervals);
}

}

Coded
Review Needed
Time Complexity O(N^2)
Space Complexity O(1)
Run Here http://ideone.com/QJIqx

WAP Check Endianess of Machine & Converting From One Endians To Other

First of all, Do you know what Little-Endian and Big-Endian mean? Little Endian means that the lower order byte of the number is stored in memory at the lowest address, and the higher order byte is stored at the highest address. That is, the little end comes first.
This Question Is Frequently Asked in Top Core Companies Interviews so you need to aware of Computer System Architecture

For example, a 4 byte, 32-bit integer
Byte3 Byte2 Byte1 Byte0
will be arranged in memory as follows:

Base_Address+0 Byte0
Base_Address+1 Byte1
Base_Address+2 Byte2
Base_Address+3 Byte3
Intel processors use “Little Endian” byte order.

“Big Endian” means that the higher order byte of the number is stored in memory at the lowest address, and the lower order byte at the highest address. The big end comes first.

Base_Address+0 Byte3
Base_Address+1 Byte2
Base_Address+2 Byte1
Base_Address+3 Byte0
Motorola, Solaris processors use “Big Endian” byte order.

In “Little Endian” form, code which picks up a 1, 2, 4, or longer byte number proceed in the same way for all formats. They first pick up the lowest order byte at offset 0 and proceed from there. Also, because of the 1:1 relationship between address offset and byte number (offset 0 is byte 0), multiple precision mathematic routines are easy to code. In “Big Endian” form, since the high-order byte comes first, the code can test whether the number is positive or negative by looking at the byte at offset zero. Its not required to know how long the number is, nor does the code have to skip over any bytes to find the byte containing the sign information. The numbers are also stored in the order in which they are printed out, so binary to decimal routines are particularly efficient.
Here is some code to determine what is the type of your machine

int num = 1;
if(*(char *)&num == 1)
{
printf("\nLittle-Endian\n");
}
else
{
printf("Big-Endian\n");
}

And here is some code to convert from one Endian to another.

int myreversefunc(int num)
{
int byte0, byte1, byte2, byte3;
byte0 = (num & x000000FF) >> 0 ;
byte1 = (num & x0000FF00) >> 8 ;
byte2 = (num & x00FF0000) >> 16 ;
byte3 = (num & xFF000000) >> 24 ;
return((byte0 << 24) | (byte1 << 16) | (byte2 << 8) | (byte3 << 0));
}

1st is fibonacci
2nd pattern matching

WAP to print All Path That Sums Up to Given value In Binary Tree

Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number.

Special Case 1 what happen if got sum=0 in the mid before reaching to leaf nodes.?
Special Case 2 what happens if path not starts from root..?? More Important

Status: Modification Needed

#include
#include
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*
Given a tree and a sum, return true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum.

Strategy: subtract the node value from the sum when recurring down,
and check to see if the sum is 0 when you run out of tree.
*/

void printArray(int ints[], int len)
{
int i;
for (i=0; i {
printf("%d ", ints[i]);
}
printf("\n");
}


void hasPathSum(struct node* node, int sum,int ar[],int index)
{

if(node==NULL)//Tree Empty
return;

/* return true if we are not run out of tree and sum==0 */
if(sum==0)
{
printArray(ar,index);//case arrive when we haven't traversed the tree but foun
//the path before reaching the leaf nodes
return;
}


else
{


ar[index]=node->data;
index++;

int subSum = sum - node->data;

/* If we reach a leaf node and sum becomes 0 then return true*/
if (subSum == 0 && node->left == NULL && node->right == NULL )
printArray(ar,index);
if(node->left)
hasPathSum(node->left,subSum,ar,index);
if(node->right)
hasPathSum(node->right, subSum,ar,index);

}
}


void hasPath(struct node* root, int sum)
{
int ar[100];
hasPathSum(root,sum,ar,0);

}

/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newnode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{

int sum = 20;//21,10; 2nd special case 20 1st special case

/* Constructed binary tree is
10
/ \
8 2
/ \ / \
3 2 9 4
*/
struct node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(2);
root->left->left = newnode(3);
root->left->right = newnode(2);
root->left->right->left = newnode(1);
root->right->left = newnode(9);
root->right->right= newnode(8);
root->right->right->left= newnode(5);
hasPath(root, sum);

getchar();
return 0;
}

TC O(n)
SC O(1)
Run here https://ideone.com/rnkWi
Run here For Negative Numbers https://ideone.com/HNbFo

WAP to Finds Number of Blocks in Matrix Efficiently

Given a matrix, you need to find the number of blocks in it.
A block has the same numbers.
EG:
1 1 3
1 2 3
2 2 4
has 4 blocks namely,
1 1
1
2
2 2
3
3
4
1 2 3
4 5 6
7 8 9
has 9 blocks
1 1 1
1 1 3
4 4 5
has 4 blocks,
1 1 1
1 1
3
5
4 4

Algorithm

PS:Though Think Matrix As a Rectangle/Square a Block can have only vertical or Horizontal lines , arrangements of these lines makes a block so consider matrix elements as the end points on horizontal & vertical lines.its approximate though that can give idea how to approach up to some extent.

1. so first Visit all the elements row by row
2. Compare the value of the current element with the values of the above of the
current element left.
3. Compare the value of the current element with the values of the left of the
current element left.
4. Also compare current element with diagonal element & right element no
3. If value of above element is equal to at-least one of them, don't increment
blocks number Otherwise increment blocks number




#include






int numBlocks(int m, int n, int (*a)[3]){


int i, j;

int numblocks = 0;



for(i = 0 ; i < m; ++i){

for(j = 0 ; j < n; ++j){
//for above element
if(i - 1 >= 0 && a[i - 1][j] == a[i][j]) continue;
//for left element
if(j - 1 >= 0 && a[i][j - 1] == a[i][j]) continue;
//for diagonal & right element
if(i - 1 >= 0 && j + 1 < n && a[i - 1][j + 1] == a[i][j] && a[i][j+1] == a[i][j]) continue;

numblocks++;

}
}


return numblocks;


}


int main(){

int a[][3] = {
{1, 1, 3},
{1, 2, 3},
{2, 2, 4}
};

printf("%d\n", numBlocks(3, 3, a));

}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here http://ideone.com/ZeG8i

WAP Find The Next Largest Palindrome of Given Number Need not to b Palindrome

PS: Don't Get Confused it With Finding Next Palindrome Post

Algorith

1. counts the tottal no of digits in given number & place value of MSB
placevalue will help us to find half no from MSB
2. Get the num till half of the number of digit of given num.
3. Add 1 in to it.
4. Reverse the num obtained in step 2.
5. Append the numbers obtained in 2 and 3.

#include


int nextPalindromInt(int inPalindromeInt)
{
int numOfDigit=0, placeValue=1;
int num=inPalindromeInt, halfNum=0, i;
/*Get Total num of digit and place value of most significant digit*/
while(num)
{
numOfDigit++;
num=num/10;
placeValue = placeValue*10;
}
i=(numOfDigit>>1)+((numOfDigit%2));

num=inPalindromeInt;
placeValue=placeValue/10;

//printf( " %d %d ",i,placeValue);

/*Get the num till half of the number of digit*/
while(i)
{
halfNum = halfNum*10 + num/placeValue;
num=num%placeValue;
placeValue = placeValue/10;
i--;
}
/*Add one in halfnum, get next palindrome by appending
halfNum in to halfNum in reverse manner*/
halfNum=halfNum+1;
num=halfNum;

/*if(numOfDigit%2) Used as optimization Step can be omitted
{
num=halfNum/10;
}*/

while(num)
{
halfNum=halfNum*10 + num%10;
num=num/10;
}
return halfNum;
}

int main()
{

printf("%d",nextPalindromInt(123456));
return 0;
}



TC O(K) k length of number
SC O(1)
Run Here https://ideone.com/FpgEj

WAP to Traverse The Binary Tree In ZIG ZAG Order or Spiral Order

This Problem Can be Solved In Two Ways
1 By Recursion by Modifying Level Order Traversal
2.By Using two Stack


To Traverse the Tree in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable alter is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.


Method 1 Using 2-Stack--Need Modification RunTime Error But Logic is 100% Correct

#include
#include

/* Structure for Tree */
struct node
{
struct node* left;
struct node* right;
int data;
};

/* structure of a stack node */
struct sNode
{
struct node *t;
struct sNode *next;
};

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct node* newtNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct node *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref);

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}

/* Function to pop an item from stack*/
struct node *pop(struct sNode** top_ref)
{
struct node *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}

void Insert(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->left= NULL;

/* link the old list off the new node */
new_node->right= (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->left= new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}

void Spiral(struct node* root)
{
struct node *head;//for DLL
struct sNode *node1;
struct sNode *node2;
struct node *temp;


if(root == NULL)
return;

push(&node1,root);


while(!isEmpty(node1) && !isEmpty(node2))
{

while(!isEmpty(node1))
{
temp = pop(&node1);
Insert(&head,temp->data);
push(&node2,temp->right);
push(&node2,temp->left);
}
//temp=NULL;

while(!isEmpty(node2))
{
temp = pop(&node2);
Insert(&head,temp->data);
push(&node1,temp -> left);
push(&node1,temp -> right);
}

}

}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Utility function to print a linked list */
void printList(struct node* head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->right;
}
printf("\n");
}

/* Driver function to test above functions */
int main()
{
struct node *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
root->right->left = newtNode(6);
root->right->right = newtNode(7);

Spiral(root);
printList(root);

getchar();
}

TC O(n)
SC (n) if Stack Space is considered else O(1)
Run Here https://ideone.com/cyPM5



Method 2 Using Recursion ( Modified Level Order Traversal)

Algorithm:

Function to print level order traversal of tree


printSpiralorder(tree)
bool alter= 0;
for d = 1 to height(tree)
printGivenOrder(tree, d, alter);
alter~= alter/*flip ltr*/
Function to print all nodes at a given level

printGivenOrder(tree, level)
if tree is NULL then return;
if level is 1, then
print(tree->data);
else if level greater than 1, then
if(alter)
printGivenOrder(tree->right, level-1, alter);
printGivenOrder(tree->left, level-1, alter);
else
printGivenOrder(tree->left, level-1, alter);
printGivenLevel(tree->right, level-1, alter);

Implementation:


#include
#include
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*Function protoypes*/
void printGivenLevel(struct node* root, int level, int ltr);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print spiral traversal of a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;

/*ltr -> Left to Right. If this variable is set,
then the given level is traverseed from left to right. */
bool Alter= 0;
for(i=1; i<=h; i++)
{
printGivenLevel(root, i, Alter);

/*Revert ltr to traverse next level in oppposite order*/
ltr = ~ltr;
}
}

/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level, int Alter)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
if(ltr)
{
printGivenLevel(root->left, level-1, Alter);
printGivenLevel(root->right, level-1, Alter);
}
else
{
printGivenLevel(root->right, level-1, Alter);
printGivenLevel(root->left, level-1, Alter);
}
}
}

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);

/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(7);
root->left->right = newNode(6);
root->right->left = newNode(5);
root->right->right = newNode(4);
printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}


TC O(N^2)
SC O(1)
Run Here https://ideone.com/XGtsZ

WAP to Find Largest Palindrome In String Difficult One & We Have to Solve it Efficiently

Algorithm

As we know a string can have even & odd length palindrome & any one of them can be larger then other so 1st we will find all odd & even length palindrome of string then we find larger of them.to find odd & even length we will do follow.

for odd length palindrome for each position in string take two variable to store index of element before current index & element after the current index & keep decrementing 1st index & incrementing 2nd index until we won't found any mismatch.save length of maximum odd length palindrome & index of this palindrome. so that in last we just need to compare the maximum odd length palindrome & maximum even lengths palindromic & in last print maximum of them by saving indexes.

class FindAllPalindromes 
{
 public static void main(String[] args)
 {
  FindAllPalindromes finder = new FindAllPalindromes();
  finder.printAllPalindromes("rorradarpottopradarradar");
 }
  
 public void printAllPalindromes(String inputText)
 {
  int cur1=0,max1=-1,cur2=0,max2=-1,a=0,b=0,c=0,d=0;
  if(inputText==null)
  {
   System.out.println("Input cannot be null!");
   return;
  }
  if(inputText.length()<=2)
  {
   System.out.println("Minimum three characters should be present");
  }
  //ODD Occuring Palindromes
  int len = inputText.length();
  for(int i=1;i<len-1;i++){
   for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k))
    { 
      cur1=k+1-j;
      if(max1<cur1)
      {
        max1=cur1; a=j;b=k+1;
       //System.out.println(inputText.subSequence(j,k+1));
      }
    }else{
     break;
    }
   }
  }
  //EVEN Occuring Palindromes
  for(int i=1;i<len-1;i++)
  {
   for(int j=i,k=i+1;j>=0&&k<len;j--,k++)
   {
    if(inputText.charAt(j) == inputText.charAt(k))
    {
       cur2=k+1-j;
      if(max2<cur2)
      {
        max2=cur2;c=j;d=k+1;
       //System.out.println(inputText.subSequence(j,k+1));
      }
    }
     else
     {
         break;
     }
   }
  }
    if(max1>max2)System.out.println(inputText.subSequence(a,b));
    else System.out.println(inputText.subSequence(c,d));
 }
}

Time Complexity O(N*M)
Space Complexity O(1)
Run Here https://ideone.com/6Zwes

One More Interesting Explanation I Found Here
http://stevekrenzel.com/articles/longest-palnidrome