kumar.akshay
BAN USERFirst partition on 'A', based on ascii value of these characters.. that should return the index of 'A'.
and then right side will be alphabet, left would be numerics.. quick_sort the alphabet part (index of 'A' ...end)...and add the numerics (0.. index of 'A') and move to the end.
char a[] = {'C','D','E','2','W','3','A' };
char pivot = 'A',tmp;
int idx = 0, val = 0;
for(int i = 0;i<a.length;i++){
if(a[i]<pivot){
tmp = a[i];
a[i] = a[idx];
a[idx] = tmp;
idx++;
}
}
Arrays.sort(a, idx, a.length);
for(int i=0;i<idx;i++) val+=(a[i]-'0');
String ans = new String(a,idx,a.length-idx)+val;
System.out.println(" "+ ans);
Further elaborating your solution,
if original structure is not to be modified, and just to be printed rotated..then:
new (p,q) = (j, N-i-1)
so j=p, i=N-q-1.
code:
for p = 0..N
for q = 0..N
print matrix[N-q-1][p];
print "\n"
May be they are looking for this
(defun sum-list (list)
(if list
(+ (car list) (sum-list (cdr list)))
0))
So, when taking cross product of outer elements with returned subsets of sub problem..
only consider non-trivial solutions (non rows/columns), which form disjoint sets and no two points are on same row/column.
Choosing minor matrix for inner solution ensures that when taking product, no inner subset would lie on same row/column..
Matrix approach is good.
Here is the formula that I derived by hit and trial...
for n = 1, there are two such sets, (1), (1).
for n = 2, there are 2*2+f(1) = 6...
e.g. for
12
34
12, 34,13,24 + (1) paired with disjoint sets of minor matrix of 1, (2) paired with disjoint sets of minor matrix of (2)..
*Minor matrix of (aij) = matrix formed by deleting rows and columns corresponding to aij..
Similarly, for n=3
e.g.
123
456
789
there are 2*n rows and column sets.. for others, we do recursively..
(1) paired with disjoint sets of minor matrix {(5,6), (8,9))..
(2) paired with disjoint sets of minor matrix {(4,6),(7,9)}
(3) paired with disjoint sets of minor matrix {(4,5),(7,8)}
So, all inner loops of recursive calls have to return disjoint sets.. only outer multiplication will allow for for 1 duplicate.... when pairing with outer elements
Another key thing while returning disjoint sets.. no two elements should not be on same row or column, otherwise it will intersect with row/column zones...
So, recurrence relation becomes
F(n) = 2*n + n*(n-1)
= 2n + n^2 - n = n^2 + n.
I agree on the '7' shape thing, for dimensions higher than 3, 7 shape does not work, or in other words '7' shape looses its meaning (becomes too ambiguous)..
- kumar.akshay June 03, 2012The idea is, there are 2*N (for NxN matrix ) +2 trivial solutions (N columns, N rows, and two diagonals), and we have to figure out other solutions.. which are zones of N numbers, and which do not share more than 1 points with any other existing solutions....
And this can be solved recursively, when we do.....
for each element of first row ( or first column)...figure out disjoint non-trivial solutions of minor matrix of that element.
* minor matrix of a given element is defined as - sub-matrix formed by excluding that row and that column.