sachin
BAN USERCan be done by swapping elements one by one of the 1st row and 1st column and then recursively passing the rest of the matrix (excluding 1st row and 1st column).
// rs -row start
// cs - column start
// re - row end
// ce - col end
3 void transposeMat(int** a, int rs, int cs, int re, int ce) {
4 int rows = re-rs;
5 if (rows==0)
6 return;
7
8 int i, t;
9 for (i=rs; i<=rows; i++) {
10 t = a[i][cs];
11 a[i][cs] = a[cs][i];
12 a[cs][i] = t;
13 }
14
15 transposeMat(a, rs+1, cs+1, re, ce);
16 }
View the input as a bit vector. Then, it is about enumerating a bit vector of size n.
Idea:
Input: "cab"
1. Recursively call the function each time trimming one character (trim c, then a)
2. When the length of the string reaches 1, return an empty string and one length character. Like ("", "b")
3. For each of the item returned from the recursion, create two items: 1. same item 2. add the trimmed character
Like: ("", "a", "b", "ab")
4. At the end, we will have all the combinations.
Here is the python code:
1 #! /usr/bin/env python
2 import sys
3
4 def generateCombination(inp):
5 if len(inp) == 1:
6 return [[],[inp[0]]]
7
8 myContrib = inp[0]
9 rest = generateCombination(inp[1:])
10 result = []
11 for aCombination in rest:
12 s = aCombination[:]
13 t = aCombination[:]
14 t.append(myContrib)
15 result.append(s)
16 result.append(t)
17
18 return result
19
20 if __name__ == '__main__':
21 inp = map(lambda x : int(x), sys.argv[1].split(" "))
22 result = generateCombination(inp)
23 for anItem in result:
24 print anItem
Sanjay, I think the number may not be necessarily in the row/column of 8/12.
Consider this array:
1 5 6 10
2 8 9 15
3 11 12 20
4 15 16 25
Here 10 lies between 8 and 12 but, not in the row/column of 8/12.
As someone below pointed out, each time, we can only eliminate one quarter of the input. In this case, we can eliminate
1 5
2 8
The first part of the problem can be solved using dynamic programming which builds on string prefix. It is very similar to the longest common sub sequence problem.
Here, the columns will be the given array and the rows will be 1 to k. So any point in the matrix (row, column) says, if 'column' element is included in the window, what is the window size (that much characters to the left).
Finally after constructing the table of size k*n, where n is the length of the array, the minimum element in the kth row will give the position in the input array where the smallest windows (containing k 0's) ends and its value indicates the size of the window.
Recursion relation:
SmallestWindow( length, k ) =
= SmallestWindow (length-1, k-1) + 1 if input[length] == 0 (contributes one zero)
= SmallestWindow (length-1, k) + 1 if input[length] == 1 (simply adds length)
This is exactly like converting a string to int.
While converting a string to integer, initially we keep the result as zero. Then multiply result by 10 and add the current digit (corresponding to the current character) to the result; We keep doing it until all the characters in the input string are visited.
The only change to this problem is,
1. We have to map the character from A-Z to 1-26
2. Start with result=0 and multiply result with 26 and then add the digit value corresponding to the current character.
Suppose if the input is 'BAD', then,
1. result = 0
2. result = (result*26) + 'B'-'A'+1 (adding 1 at the end so as to map 'A' to 1)
3. result = (result*26) + 'A'-'A'+1
4. result = (result*26) + 'D'-'A'+1
return result.
If there are 'n' papers in total, this problem can be solved in O(n) with space complexity of O(n). Note that, h-index can be between 0 to n. Say if the h-index is 10, this means, there has to be 10 papers with citation count >= 10. So if we can find out the number of papers with citations >=X for every X (and store it in an array C) where X ranges between 0 to n, then by scanning the count array C from the right to left, we can find the h-index at index i where i == C[i].
- sachin September 07, 2012Pseudocode:
input array A of length n.
- init array C[0] to C[n] with 0
- foreach p in A, if p >= n, c[n]++; else c[p] +=1
- for i=n-1 to 0, c[i]=c[i]+c[i+1]
- for i=n to 0, if c[i] == i return i