algos
BAN USERvoid reverse_single_pointer(node **head)
{
node *newone = NULL;
while(*head)
{
(*head)->link = (node*)((int)(*head)->link ^ (int)(newone));
newone = (node*)((int)(*head)->link ^ (int)(newone));
(*head)->link = (node*)((int)(*head)->link ^ (int)(newone));
*head = (node*)((int)(*head) ^ (int)(newone));
newone = (node*)((int)(*head) ^ (int)(newone));
*head = (node*)((int)(*head) ^ (int)(newone));
}
*head = newone;
}
as per the sequence the possible in-order successor could be 7. if you need to find the in-order successor with the existing data then return -1 as that doesn't exist
---------------4
-------2--------------6
----1----3-------5-------7
--------------4.5--5.5
4 is average of 2&6
2 is average of 1&3
5 is average of 4.5&5.5
6 is average of 5&7
time complexity is O(n) and space complexity is O(n)
hash the sum from 0 to i for all array elements, i.e sum[i] = sum of all elements from a[0] to a[i] and corresponding index as data to key (starting from -1 to n)
ex: 2 3 -4 9 -1 -7 -5 6 5
sum to enter in hash table : 0 2 5 1 10 9 2 -3 3 8
index to enter in hash table: -1 0 1 2 3 4 5 6 7 8
hash sum as key and its corresponding index as data. and while hashing check if any sum is already exists in hash table
here there is one duplicate number that is 2 in sum array... the indexes of duplicate numbers is 0 and 5, so we need to take sum from index 1 to 5 in original array that is 3 to -7
if there are no duplicates in sum array then sub-array with sum ZERO doesn't exists in given array
*(p+2) is more efficient...
lets the start address is 1000, *(p+2) will add 2 to base address and fetch the data at address location 1002... this one fetch the data in single step
where as p[2] move one by one location from base / start address to the desired address 1002, this one fetch the data in n steps (for p[n])
lets array length is L
reminder = n % L
reminder < (L-reminder) ? reminder : (L-reminder)
ex: 1 2 3 4 5 6 7 8 9
case 1: n = 13
reminder = 13%9 = 4
6 7 8 9 1 2 3 4 5 here 6 7 8 9 (4 numbers) are not in correct position
case 2: n = 23
reminder = 23%9 = 5
5 6 7 8 9 1 2 3 4 here 1 2 3 4 is not in correct position, here return reminder or (L-reminder) which ever is smaller
to print the numbers that are not in correct position
if(reminder < (L-reminder))
{
for(int i=0; i < reminder; i++)
cout << a[i] << " ";
}
else
{
for(int i=reminder; i < L; i++)
cout << a[i] << " ";
}
number of ways to pick any 2 socks from 24 socks = 24C2
number of ways to pick 2 BLACK socks from 12 BLACK socks = 12C2
probability of picking 2 BLACK socks = 12C2 / 24C2 = 66/276
probability of picking 2 WHITE socks = 12C2 / 24C2 = 66/276
probability of picking any 2 same color socks = 66/276 + 66/276 = 11/23
97/32 = 3 and 97%32=1, for arr[3] bit 1 will be set... arr[3] = 2
6/32 = 0 and 6%32=6, for arr[0] bit 6 will be set..... arr[0] = 64
64/32 = 2 and 64%32=0, for arr[2] bit 0 will be set... arr[2] = 1
37/32 = 1 and 37%32=5, for arr[1] bit 5 will be set... arr[1] = 32
36/32 = 1 and 37%32=4, for arr[1] bit 4 will be set... arr[1] = 16 | 32=48 (32 is bit 5 which is already set)
in first iteration algorithm finds the probable majority element. during second iteration it verifies probable majority element appears more than n/2 times or not. if it appears more than n/2 times then it will return that number else it returns -1 (no such majority element exists)
3 5 3 7 3 1 1 3
in this example 3 appears 4 times but it is not >n/2... so it returns -1 (not found)
it's O(log n) only. what is not guaranteed in your example?
{1, 99, $, $, $, $, $, $, .....}
1. k = 1 then in first if condition it finds
2. k = 99 then in first if condition it finds
3. 1<k>99 then in first if condition it returns -1 as number not found
4. k > 99 here first if condition fails so in else start becomes 2, arr[2] = '$' so it returns -1 as number not found
variation of binary search i.e.. reverse binary search.
check the target number is present in below index ranges i.e.. 2^n index range
0-1
2-3
4-7
8-15
16-31
32-63
.
.
if target number is found in any of the above range then apply binary search on data in that range
int start=0, end = 1;
int i = 1; // to apply binary search from intermediate data
if target <= a[end]
apply binary search for the range start and end
else
i *= 2;
start += i;
end += i;
if arr[start] == '$'
print(data not found)
break
else if arr[end] == '$' // start is number and end is '$' then apply BS from start
i = 1
end = start + 1
time complexity is O(log n)
Below code is to store back the data in sorted order into array
int data[20000] = {97,6,64,37}; // initially given unique data
int arr[625] = {64,32,1,2}; // bit vector array
int index = 0; // index to store back all data
for(int i=0; i<=625; i++)
for(int j=0; j<32; j++)
if(arr[i] & (1 << j))
data[index++] = i*32 + j;
use bit vector to store each integer in single bit. 625 integers are required to store 20000 numbers
int arr[625] = {0};
ex: to store data 2000
arr index = 2000/32 = 62
bit position = 2000%32 = 16
now make bit position 16 of array index 62 arr[62] to 1
using this bit vectors we can store data range from 1 - 20000 in 625 integers..
after storing all data in bit vectors, check all bit positions of arr[0], arr[1]..... arr[625]... if any bit position is set to 1 then store back that data into array
lets arr[10] bit position 15 is set to 1 then this is equivalent to data 10*32+15 = 335
arr[] = 2 -3 4 -2 3 1
sumarray[i] = sum of all elements from index 0 to i
from start index sum_array_start[] = 2 -1 3 1 4 5
from end index sum_array_end[] = 5 3 6 2 4 1
now compare all elements in both sum arrays... at one index location the data is same in both sum_arrays, that index location is the equilibrium point index a[index]...
here 4 is same for both sum arrays and it is at index 4... so a[4] i.e 3 is equilibrium point
if given array is post-order then start processing from end of the array and first insert right child and then left child
if given array is pre-order then start processing from start of the array and first insert left child and then right child
initially sz = length of array - 1 (for given post-order array)
void insert(node **root, char arr[], int &sz)
{
*root = new node;
(*root)->data = arr[sz];
(*root)->left = (*root)->right = NULL;
if(arr[sz] == 'i')
{
insert(&(*root)->right, arr, --sz);
insert(&(*root)->left, arr, --sz);
}
}
@Ayahuasca: in 2nd point compare matching bolt with all other nuts, does not means that every time it compare all n elements for each recursive call.. we will be applying recursion in each sub group, so only that subgroup exists during that run so it will compare with all elements in that subgroup only.
- algos July 17, 2013O(1) solution
number of children at even level = 4
number of children at odd level = 3
x = 1 + 4;
y = 4 * 3;
int n = (level-1)/2 - 1;
double res;
if(level % 2)
res = (pow(y, n+1)*(x+y-1)-x) / (y-1);
else
res = x + (x*y*(pow(y, n+1)-1)) / (y-1);
cout << res << endl;
below is proof
number of nodes level
1 1
4 2
4*3 3
4*3*4 4
4*3*4*3 5
4*3*4*3*4 6
4*3*4*3*4*3 7
4*3*4*3*4*3*4 8
lets take odd level at 7
1 + 4 + 4*3 + 4*3*4 + 4*3*4*3 + 4*3*4*3*4 + 4*3*4*3*4*3
1 + 4 + 4*3 ( 1 + 4 + 4*3 + 4*3*4 + (4*3)^2)
1 + 4 + 4*3 ( 1 + 4 + 4*3 (1 + 4 + (4*3))
lets take x = 1+4 and y = 4*3
this equation looks like
x + y (x + y (x + y))
x + y (x + xy + y^2)
x + xy + xy^2 + y^3
x (1 + y + y^2) + y^3
...
this is summation series x ( 1+ y + y^2 + y^3+ y^4....+y^n) + y^(n+1)
summation for 1+ y + y^2 + y^3+ y^4....+y^n = (y^(n+1) - 1) / (y-1)
answer for odd levels is x(y^(n+1)-1)/(y-1) + y^(n+1)
for even level it will be
x + xy + xy^2 + xy^3 + xy^4...
x + xy(1 + y + y^2 + y^3 + ...)
after solving the summation series for even levels is
x + xy(y^(n+1)-1)/(y-1)
answer for this question is variation of QUICK SORT.
lets there are n bolts and n nuts, you can compare nut with bolt and can tell whether bolt is smaller, bigger or equal to nut.
1. lets take a random nut and compare with all bolts. after this exercise you will get one match that will fit with nut, one group of bolts those are bigger than nut and another group which is smaller than nut.
2. now compare the matching bolt with all other nuts in the same group, here also we get two groups.. one is bigger group and another is smaller group
3. finally we get one nut-bolt match and one group of nuts and bolts those are smaller than the match nut-bolt and another group of nuts and bolts those are bigger than the match nut-bolt combination
4. now apply recursion on both smaller and bigger groups... do this till all matches found
5. finally we get nut-bolt match combinations and also those are sorted.
time complexity is O(n log n).
- algos December 04, 2013