Somisetty
BAN USERHave a goal and want to achieve it.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println(p());
}
public static boolean p() {
HashMap<Character, Character> h = new HashMap<Character,Character>();
h.put('0', '0');
h.put('1', '1');
h.put('5', '5');
h.put('8', '8');
h.put('6', '9');
h.put('9', '6');
String ip = "1691";
int len = ip.length();
for(int i=0; i < len; i++ ) {
if (i>(len/2)+1)
break;
char x,y;
Character z;
x = ip.charAt(i);
if (len == 1)
y = ip.charAt(0);
else
y = ip.charAt(len-1-i);
z = h.get(x);
if (z!=null && y == z)
continue;
else
return false;
}
return true;
}
}
i did not read gnahzy's program, But here is the approach that will give
Best case: O(logn)
worst case m * O(longn) (i.e ~O(logn) )
1. on the first row, do a binary search till you find a 1.
2. 1 found on the first row is at say index i.
3. Move to next row, and see if the element directly below arr[0][i] is 1 or not.
4. if it is 1, repeat step 1 again. If not skip to next row.
The last row on which we found 1 sucessfully is the correct answer.
Best case: first row in the matrix has the highest number of 1's ~ O(logn)
Wors Case: The entire matrix does not have 1's at all. ~ number of rows x O(logn)
Here is my soluion:
if its BST of integers, the preorder will look like this
ex:
4
26
1357
preorder: 4-2-1-3-6-5-7
1. the first number to read is denoted as head.
2. create a new variable called leftheight and init to zero.
3. continue reading integers from the stream.
4. check if the number read just now, is smaller than the number read before it.
5. if Yes, leftheight++. goto step 4.
6. If No, check if the integer read now is also greater than head (read in step 1)
7. If Yes, the new number we read just now is head of right subtree. repeat steps 1-6 to get height of right subtree and compare it with leftheight, whichever is the highest is the height of the tree. algorithm ends.
8. If No, we have just completed a subtree of a main tree and now moving to the right part of it.
From here on, leftheight should be updated only if the righttree reports more height then already recorded value.
i will try to comeup with a program (mostly recursive one to solve this)
can you clarify the following?
if page break is happening only once, then what do you mean by return all positions of pixels?
Do you mean breaking the matrix in to multiple pages such that all rows between two white rows are skipped?
Also, if its a Nx1000 matrix isn't it mean N rows and 1000 columns or do you mean to say NxN matrix with N is atmost 1000?
Regards
if all numbers are unique means allowed values for N are 1-9, and assuming positions range from 1-N (from left to right) here is a recursive solution. The main rule is the numbers allowed for ith position are i<->9-(N-i)
my solution uses lot of stack space than laxmi's because string object is sent from call-to-call.
BTW, initiating call should be printSeq(1, 0, s);
int N = 3;
void printSeq(int i, int prevValue, string pResult)
{
if(N<1 || N>9) return;
int lowEnd = prevValue + 1;
int highEnd = 9-(N-i);
if(highEnd < prevValue)
return;
for(;lowEnd<=highEnd;lowEnd++)
{
char ch = '0'+lowEnd;
stringstream temp;
string newResult;
temp << pResult;
temp << ch;
temp >> newResult;
if(newResult.length() == N)
cout<<newResult<<"\n";
else
printSeq(i+1, lowEnd, newResult);
}
}
Apart from the above mentioned complications, there is one more danger. i.e one addition of class as parent at top of hierarchy can easily bloat the size of objects at child level. This is one reason why embedded systems (like Symbian) allways try to put restriction on multiple inheritance.
- Somisetty November 29, 2011
recursive depth first search is the way to go (with extra checks for wall, corresponding to leaf nodes of a graph).
- Somisetty November 11, 2015The solution has to be recursive because the API's provided has to be used, Adjacent node generation is done by 'turning' and bread crumb is used to visit.