shashank.neo
BAN USERpublic class JumbledNumbers {
private final int[][] jumbledGraph = new int[][]{
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0}};
public void printJumbledNumber(int n) {
int num = n;
int maxLetters = 0;
while (num > 0) {
maxLetters++;
num /= 10;
}
for (int i = 2; i <= maxLetters; i++) {
Stack<Integer[]> s = new Stack<>();
//s.push(new Integer[]{0, 0, 0});
s.push(new Integer[]{1, 1, 0});
s.push(new Integer[]{2, 1, 0});
s.push(new Integer[]{3, 1, 0});
s.push(new Integer[]{4, 1, 0});
s.push(new Integer[]{5, 1, 0});
s.push(new Integer[]{6, 1, 0});
s.push(new Integer[]{7, 1, 0});
s.push(new Integer[]{8, 1, 0});
s.push(new Integer[]{9, 1, 0});
while (!s.isEmpty()) {
Integer[] step = s.pop();
int number = step[2] * 10 + step[0];
if (step[1] < i) {
for (int k = jumbledGraph[step[0]].length - 1; k >= 0; k--) {
if (jumbledGraph[step[0]][k] == 1) {
s.push(new Integer[]{k, step[1] + 1, number});
}
}
} else {
if(number < n) System.out.println(number);
}
}
}
}
public static void main(String[] args) {
JumbledNumbers jumbledNumbers = new JumbledNumbers();
jumbledNumbers.printJumbledNumber(100000000);
}
}
void BSTtoDLL(node* root, node* &left, node* &right){
if ( root ){
node *left1=0,*right1=0,*left2=0,*right2=0;
BSTtoDLL(root->left,left1,right1);
BSTtoDLL(root->right,left2,right2);
if(right1){
right1->right=root;
root->left=right1;
}
if(left2){
root->right=left2;
left2->left=root;
}
if (left1)
left=left1;
else
left = root;
if (right2)
right=right2;
else
right=root;
}
}
I guess constant space means you have to modify the tree, not to traverse and build a DLL. This question can be solved using inorder traversal(as in above codes) or post order traversal of tree.
- shashank.neo February 07, 2012Awesome solution!!!!
- shashank.neo February 07, 2012#include<iostream>
using namespace std;
int main(){
char str[1000];
while(cin>>str){
if(!next_permutation(str,str+strlen(str)))
cout<<"-1\n";
else
cout<<str<<"\n";
}
}
- shashank.neo June 19, 2016