WAP to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.You have an array of 0s and 1s. Efficiently

Example
 
pos = 0 1 2 3 4 5 6 7 8
 
arr = 0 1 0 0 1 1 1 1 0
 
One interval is (0, 1) because there the number of 0 and 1 are 
equal.There are many other intervals, find all of them in linear time.
  
A naive Algorithm will take O(N^3) of time find all such interval 
if wont pre-process till auxiliary array x (where each x[i] will0 
contains the cumulative sum from o to ith index)because in this 
case we need to find all i,j such that they represents equal number 
of 0s & 1s so it will take O(N^3) Time.
But This Algo Will fail for array like 1 0 1 0 1 0 1 0 
you can run here above Algo will print only few intervals 
but as i have counted contains 16 such intervals which are 
of equal numbers of 0s & 1s.
 
2nd Algorithm O(N^2) Efficient
 
Approach
 
In This question we need to find all the intervals and in worst case
no of intervals can grow as large as O(n^2) so hashing will not work
we need to form as adjacency list type of thing :(
 
here what i m trying to do is after calculating the array x if any x[i]
is zero means that that sum of elements from 0 to i is zero hence it
contains equal no of zeros and ones. so for every x[i] = 0 [0,i] is 
a solution, ans also for every x[i] and x[j] if(x[i] == x[j]) implies
that sum does not changes from x[i] to x[j] hence equal no of 0's and
1's [i+1,j].
 
now what i think is finding all the intervals is going to be O(n^2)
 
1.Pre-processing Step
a.Replace all zeros with -1
b.calculate cumulative array X such each x[i] represents the sum from 0
 to ith index in array A
2.Check for every ith index in X array if
a. x[i]==0 then we have found the interval in 0 to i
b. else check for every i if x[i]==x[j] then print the interval from i+1toj
 

#include <iostream>
using namespace std;
 
void isASolution(int i, int j){
    cout << "Interval [" << i << "," << j <<"] contains equal no of 0's and 1's\n";
}
 
void Solve(int a[], int size){
    // replacing 0 with -1
    for(int i = 0; i < size; i++){
        a[i] = 2*a[i] - 1;
    }
 
    int x[100];         //x[i] contains sum of values in a from 0 to ith position
    x[0] = a[0];
    cout << x[0] << " ";
    for(int i = 1; i < size; i++){
            x[i] = x[i-1] + a[i];
        cout << x[i] <<" ";
    }
    cout << endl;
 
    for(int i = 0; i < size; i++){
        if(x[i] == 0){
            isASolution(0,i);
        }
        for(int j = i+1; j < size; j++){
            if(x[i] == x[j]){
                isASolution(i+1,j);
            }
        }
    }
 
}
 
 
int main(){
    int a[9] = {1,0,1,0,1,0,1,0};//{0, 1, 0, 1, 1, 1, 1, 0, 0};
    int n = sizeof(a)/sizeof(a[0]);
    Solve(a,n);
}
 

Time Complexity O(N^2)
Space Complexity O(1)
Run Here http://ideone.com/dF52e
 
Feel Free To Comment, Suggest new Algorithm & Optimize The Solution

Variation:Find the maximum length subarray which maximize the no of 0s and 1s.

WAP to Find Nearest Palindrome of Given Number Efficiently

Given a number u need to find a closest palindrome of a number..
Example..
For Example 7957, the nearest palindrome is 7997
if i/p is 1999 then o/p is 2002 not 1991 (Special Case)

1st I thought About By Finding the solution using this algo

Algorithm
Find the Mid Number the from mid + 1 position copy the previous digits in the number in reverse order, i.e .... copy ( mid + 1 ..... N ) positions with ( mid ......1 )
but above case fail for 1999

#include

int nearPalin(int n){
int temp = n;
int count = 0;
while(temp>0){
temp /= 10;
count++;
}
if(count%2 == 0){
count = count/2;
while(count--)
n = n / 10;
temp = n;
printf("%d",n); //testing
while(n>0){
temp = temp*10 + n%10;
n = n/10;
}
return temp;
}
else{
count = count/2;
while(count--)
n = n / 10;
temp = n;
n = n/10;
printf("%d",n); //testing
while(n>0){
temp = temp*10 + n%10;
n = n/10;
}
return temp;
}
}

int main()
{
printf("%d",nearPalin(1999));//1234567890));
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/8B7UO


So After Discussing From Some of The Friends we can solve with some efficient algorithm that will cover the all test cases.

Algorithm
Find The Mid Number & then store half number & append it into in reverse order to original.say it a.

2nd subtract 1 from mid of number & append this half number into reverse number to itself. it will show the number that is palindrome thats is less then given number.
say it b.

3rd add 1 to mid of number & then add reverse of this to itself it will represent the number thats palindrome greater then original number
say it c.

now we have to find which is near to original number so basically we have to find the minimum of 3 number.

Note: Need to Review. As This Algorithm Will Suffer With Integer Over Flow

#include
#include
using namespace std;
long long int abs(long long int a)
{
if (a>0)
return a;
return (-a);
}

int count(long long int a)
{
int count=0;
while (a>0)
{
a=a/10;
count++;
}

return count;

}
long long int reverse(long long int a)
{
long long int b=0;
while(a>0)
{
b=b*10+(a%10);
a=a/10;
}
return b;

}

long long int NearestPalindrom(long long int a,int size)
{
long long rev;

if(size%2==0)
rev=reverse(a);
else rev=reverse(a/10);

long long int num=a;

for (int i=0; i num=num*10;

num=num+rev;
return num;
}

int main()
{

long long int a;
cin>>a;
long long int num=a;

int sizea=count(a);
for(int i=0; i num=num/10;

long long int pa = NearestPalindrom(num,sizea);
long long int pb = NearestPalindrom(num-1,sizea);
long long int pc = NearestPalindrom(num+1,sizea);

int da,db,dc;
da=abs(pa-a);
db=abs(pb-a);
dc=abs(pc-a);
if (da cout< if (db cout< if (dc cout<
}

Time Complexity O(n)
Space Complexity O(1)
Run Here http://ideone.com/l1EY8

WAP to Find Number of Way You Can Climb The Stairscase

"You are climbing a staircase. Each time you can either take one step or two. The staircase has n steps. In how many distinct ways can you climb the staircase?"

Algorithm & Approach
is I got the problem correctly then its really nice recursive problem that can solved using F(n)=F(n-1)+F(n-2) recurrence solution as its given that we can either can goto 1 step or 2 step so its just like calculating Fibonacci number using recursion which has exponentiation time complexity . we can initialize f(0)=0 & f(1)=1 as 1st pretty clear that when we are at ground floor we don't need any step to climb & to climb on next staircase up we need only 1 step from 0th staircase. so we start in from n=2 calculate nth Fibonacci number will gives us number of distinct ways can you climb the staircase.

To Calculate The nth Fibonacci Number All Possible & Optimized Solution I have posted in This Post

http://shashank7s.blogspot.com/2011/03/wap-fro-fibonacci-numbers.html

Data Structure Used: Array is Sufficient

Time Complexity O(logn)Most Efficient
Space Complexity O(n)

WAP to Print All Possible Combination of Given Number From The Given Set "Only".

Given a set of numbers eg:{2,3,6,7,8}.Any one who is playing the game can score points only from this set using the numbers in that set. given a number, print all the possible ways of scoring that many points. Repetition of combinations are not allowed.
eg:
1. 6 points can be scored as
6
3+3
2+2+2

2. 7 can be scored as
7
2+2+3
but 2+3+2 and 3+2+2 is not allowed as they are repetitions of 2+2+3 & so on

3. 8 can be scored as
2+2+2+2
2+3+3
2+6
8

& so on

Algorithms is Pretty Clear if I understand the problem clear, i have already posted the same question with slight modification in which we are not restricted by array elements but we have to print all possible combinations without duplication such that
makes the given sum.

Algorithm

Here is What we do the same keep adding the array value into current-sum until it becomes equals to desired sum isn't it while checking array value is not equals to 0 (as zero don't counts in sum simple )& array values should be <= desired-sum so that we can get all combinations.& repeat the same process until we run out of array.


class PrintAllCombinations
{

public static void main(String[] args)
{
int s = 9;
//int[] a = new int[] {2,3,6,7,8};
int[] a = new int[] {2,3,6,7,8,0,10,66,45,3,56,89};
getCombinatsions(a, 0, s, 0, "");
}

static void getCombinatsions(int[] a, int j, int desiredSum, int currentSum, String st)
{
if(desiredSum == currentSum) {
System.out.println(st);
return;
}


if(currentSum > desiredSum)
{
return;
}



for(int i = j; i < a.length; i++)
{
if (a[i] <= desiredSum && a[i] != 0)
getCombinatsions(a, i, desiredSum, currentSum + a[i], st + "+" + a[i]);
else
break;
}
}


}


Time Complexity (N*2)
Space Complexity O(logn)
Run Here http://ideone.com/x2ICo

Suggestion/Comments are Welcome.??

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