There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

Circus Problem

find the atleast one row which neither contain the maximum or the minimum element among all the elements present

Given 2D array is given of order N x N . And it is
filled with distinct elements . Now you have to find the atleast one
row which neither contain the maximum or the minimum element among all
the elements present . The runtime complexity should be less than
O(N^2) .

Naive Solution Will Gothrough All The Row & Coulumn & keep track of min , max .finally return the row that doesn't contain the max or min can't we do better ?

So Mathematically Lets Consider a Set S consisting of any three rows R1, R2, and R3, and compute the min and max of the elements in these rows.

Since all elements are distinct, at most one the three rows
will contain minimum (say R1), and at most one row will
contain maximum (say R2). This means R3 contains neither
max, nor min..

formaly We do not need to look at other rows, as inclusion of other
rows in S, will not make R3 contain max or min.

Correctness of Algorithm: Why We are processing only three row its not making things clear ? How we can sure that from N*N matrix ,if max/min won't be in out of any row from 3 row then it won't contains the max/min from N rows ? e.g. Why it will work that a row that does not contains min/max in N*N matrix will definatly be from one of the threes rows only ?

Things That Strikes In Mind is that as we need to find only 1 min & 1 max (tottal two objects) what can be the possibilities ? hey we wants to extract only two objects out of n*n objects ? what don't pprocess only n+1 rows so that if we are able to cover the all test cases , can be sure that it will satisfy the N*N as well ?

so basically our task reduce to iterate over three rows only & Find the minimum and maximum element from the elements By reading 3 rows.so 2 cases possible.

1. Min and Max element belong to 1 row
2. Min and Max belong to 2 rows

As Said Above using Set.

In both the cases we can get the row which do not contain minnimum and
maximum element from the 3 rows read. If that row does not contain
minimum and maximum element from 3 rows, it won't contain maximum and
minimum element from N rows

lets write 6*6 matrix , try to change the position of min/max , try to test it different test cases , you will find our algorithm will work &b thats work efficiently :)

Time Compelxity O(M^2) where M=3 , differ from N
its Important Questuion & All Things that we have done so far.
we are process only 3*3 sub-matrix . so lest say we have given matrix of size N*N . lets define M=3 & N=k+M where K is N-3 or N-M as i have assigned M to value 3 . so tottal time compexlity will be O(M*M) where M=3 Which is Obviously Much less then N*N isn't it . lets say N=1 million then N^2 will be 1 trillion but m^2 willl be 9 only isn't it its awesome reduction in time compelxity :)


writing the code is not big task for this only designing efficient algo matters.

Correct me if any issue with Time Complexity :)

Find the number of ways of writing a number as the sum of positive integers?

Above is Also called the Partition Function P of n, it is denoted by P(n).

For example,5 can be written as.

5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1


The partitions of 4 are listed below:

1. 4
2. 3 + 1
3. 2 + 2
4. 2 + 1 + 1
5. 1 + 1 + 1 + 1

The partitions of 8 are listed below:

1. 8
2. 7 + 1
3. 6 + 2
4. 6 + 1 + 1
5. 5 + 3
6. 5 + 2 + 1
7. 5 + 1 + 1 + 1
8. 4 + 4
9. 4 + 3 + 1
10. 4 + 2 + 2
11. 4 + 2 + 1 + 1
12. 4 + 1 + 1 + 1 + 1
13. 3 + 3 + 2
14. 3 + 3 + 1 + 1
15. 3 + 2 + 2 + 1
16. 3 + 2 + 1 + 1 + 1
17. 3 + 1 + 1 + 1 + 1 + 1
18. 2 + 2 + 2 + 2
19. 2 + 2 + 2 + 1 + 1
20. 2 + 2 + 1 + 1 + 1 + 1
21. 2 + 1 + 1 + 1 + 1 + 1 + 1
22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Approach

One way of getting a handle on the partition function involves an intermediate function p(k, n), which represents the number of partitions of n using only natural numbers at least as large as k. For any given value of k, partitions counted by p(k, n) fit into exactly one of the following categories:

1. smallest addend is k
2. smallest addend is strictly greater than k.

The number of partitions meeting the first condition is p(k, n − k). To see this, imagine a list of all the partitions of the number n − k into numbers of size at least k, then imagine appending "+ k" to each partition in the list. Now what is it a list of? As a side note, one can use this to define a sort of recursion relation for the partition function in term of the intermediate function, namely

1+ sum(P(k,n-k)=P(n)
for i=1 to floor n/2
where |_n_| is the floor function.

The number of partitions meeting the second condition is p(k + 1, n) since a
partition into parts of at least k that contains no parts of exactly k must have all parts at least k + 1.

Since the two conditions are mutually exclusive, the number of partitions meeting either condition is p(k + 1, n) + p(k, n − k). The recursively defined function is thus:

* p(k, n) = 0 if k > n

* p(k, n) = 1 if k = n

* p(k, n) = p(k+1, n) + p(k, n − k) otherwise.

Got The Hint of DP using matrix of P[n,n] :)

Euler invented a generating function which gives rise to a recurrence equation in P(n),

Design a function getBits that gives x bits from a given position p of a given number n.

Approach

So we need mask for any bit set (10010011 etc). you want to generate a "mask" that pulls only the bits you want to see. So 10010011 or 0x03, I'm interested in xxxxx011. What is the mask that will extract that set ? 00000111 Now I want to be sizeof int independent, I'll let the machine do the work i.e. start with 0 for a byte machine it's 0x00 for a word machine it's 0x0000 etc. 64 bit machine would represent by 64 bits or 0x0000000000000000

Algorithm

Now apply "not" (~0) and get 11111111
shift right (<<) by n and get 11111000 and "not" that and get 00000111 it can be written as ~( ~ 0 << x )........(1) Okay we got our mask. 1. Now, we push the bits we want out of the number into the lowest order bits so we shift binary n by p+1-x ------(2) e.g. n >> p+1-x because so it's just a clever way to get n 1-bits in the least significant part of the number.

The "x bit" you describe has shifted the given number n right far enough so that the least significant x bits are the ones you want

take the and operation of above two you will that the number represented by that x bits or we can also return the bits if save that in to string or array

so we have to finally return ( ( n >> p+1-x ) & ~( ~ 0 << x )) so Here is Working Code for the same #include

unsigned int getbits(unsigned int x, int p, int n)
{
return (x >> (p + 1 - n)) & ~(~0 << n);
}
int main(void) {
int x = 182, p = 2, n = 5;
int z = getbits(x, p, n);
printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);
//% u for unsigned & %x for hexadecimal numbers


return 0;
}

Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/eglaQ

Given 3 input strings S1, S2, S3 for example take s1 = "hard" s2 = "work", s3 = "success" assign numeric values (0-9) to each of the characters in these strings such that equation s1 + s2 = s3 holds true. Constraints are that all occurrence of a letter should be assigned the same digit. Return -1 if not possible.

Find The Cubical in 3d Matrix of m*n*o Efficiently !!!!

Given a 3D matrix of m*n*o dimension and there lies a cubicle in each cell of the matrix. Assume K cubicle are occupied(you know the coordinates of occupied cubicles) and remaining are vacant. You have to arrange a meeting. So find a cubicle such that the sum of the distances traveled by all the persons should be minimum. A Person can't move diagonally, they can only parallel to axes...

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram. This question is the last question from 2003/2004 ACM International Collegiate Programming Contest, Univ. of Ulm Local Contest. It's one of the 2 hard ones in this question set

k distinct integers [0, N) Select a random no [0,N) which is not in this k distinct list. Example: [4, 6, 9] Choose a random no between 0 - 9 which is not 4, or 6, or 9. Valid output: 2 Invalid output: 6

k distinct integers [0, N) Select a random no [0,N) which is not in this k distinct list. Example: [4, 6, 9] Choose a random no between 0 - 9 which is not 4, or 6, or 9. Valid output: 2 Invalid output: 6