CareerCup

It is very simple problem. For every start to end first digit, we need to create a tree. For example 500000 to 600000 is given range that we need to create a binary tree where left child is one less than the parent digit and right child is 1 greater the parent digit.

After the tree constructed, take root and do all traversal to all possible leaf at level count ( decimal points of start ) and generate a number for such branch.

Check is this number is in limit, if yes print it. Like this keep doing till the first digit <= last. No need to do traverse like this for(int i=start;i<end+1;i++).

public class SpecialPropetyNos {
	public static void main(String[] args) {
		int Limit = 4;
		for (int nos=0;nos<10;nos++){
			generateNos(nos, (Limit-1));
		}
	}

	private static void generateNos(int nos, int limit) {
		if (limit == 0){
			System.out.println(nos);
			return;
		}
		if ( nos%10 != 9)
			generateNos( ((nos*10)+ (nos%10+1)), (limit-1) );
		
		if( ((nos%10)-1 ) > -1 ){
			generateNos(((nos*10)+(nos%10-1)), (limit-1));
		}
	}
}

"You are given a range", what range, can you explain more?

#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
	//long l=8987656;
	long l=89876564;
	long temp_num = l;
	int prev = -1;
	int cur;
	bool isSpecial=true;
	while(temp_num)
	{
		cur = temp_num%10;
		temp_num = temp_num/10;
		if (prev == -1)
			prev = cur;
		else
		{
			if(cur != prev+1 && cur != prev-1)
			{
				isSpecial = false;
				break;
			}
			prev = cur;
		}
	}
	cout<<"Number "<<l<<" is special? "<<isSpecial;
}

//function to check weather the given number satisfies the property
//i.e 8987656 returns true
//ie.8987657 returns false

//for number 8987656 val1= 5 and val2=6 for first iteration.

bool findProperty(int num)
{

int val1=0;
int val2=-1;

while(num>0)
{
val1=num%10;
num=num/10;

if(val2!=-1)
{
int result=val1-val2;
if(result ==1 || result ==-1)
{

}
else
return false;
val2=val1;
}
else
val2=val1;


}
return true;
}

findnumbaer()
{
for (int i=range_start;i<=range_end;i++)
{
bool flag=findProperty(i);
if(flag)
std::cout<<i;
std::endl;

}

}

Please correct if I am wronge.

public class glassdoor2{

public boolean check(int i){
	int prev=i%10;
	int curr;
	i=i/10;
	while (i>0)
	{
		curr=i%10;
		if ((prev-curr==1)||(prev-curr==-1))
			prev=curr;
		else 
			return false;	
			
		i=i/10;	
	}
	
	return true;
}

public void compute(int start,int end)
{
	for(int i=start;i<end+1;i++)
	{
		if(check(i))
			System.out.println(i);
	}
}

public static void main(String[] args){
	glassdoor2 g = new glassdoor2();
	g.compute(1000,400000);
}

asymptotic solution is O(n*d). worst case O(n2).

This can be quite easily done by recursion. This is an interview question, and not a real life example. So the emphasis is on doing something elegant, not long. Here is a recursive solution that accomplishes this:

void specialNum(int num, int st, int end) {
    if (num > end)
        return;

    if (num > st) cout << num <<" ";

    int digit = num % 10;

    if (digit < 9)
        sn(num*10+digit+1, st, end);

    if (digit > 0)
        sn(num*10+digit-1, st, end);
}

void specialNum(int st, int end) {
    for (int i=1; i < 10; i++)
        sn(i, st, end);
}

int main() {
	int startRange = 10, endRange = 200000;
	specialNum(startRange, endRange); //will print out numbers as specified in question
	return 0;
}

package com.trails;

public class NumberGenerator {
	static int start = 4565676;
	static int end = 8987656;
	
	static int sDigit;
	static int eDigit;
	
	public static int getDigit(int number){
	    int counter = 0;
	    while(number != 0){
	       counter++;
		number = number / 10;
	     }
		return counter;
	}
	
	public static int getFirstDigit(int number){
		while(getDigit(number) != 1){
			number = number / 10;
		}
		
		return number;
	}
	
	public static void main(String[] args) {
		sDigit = getDigit(start); // Find total number of Digit
		eDigit = getDigit(end); // Find total number of Digit
		
		int firstNode = getFirstDigit(start); // Get first digit of end
		int lastNode = getFirstDigit(end); // Get first digit of end

		// Till first digit <= last digit
		while(firstNode <= lastNode){
			generateNumbers(firstNode, firstNode, 1);
			firstNode++;
		}
	}

      private static void generateNumbers(int number, int currentNode, int digit) {
	      // if current number of digits are more than start digits and number is in range
	     if(digit >= sDigit && number >= start && number <= end){
			System.out.print(number+ ",");
			return;
		}
		
		// If number contains more digits than the end stop immediately
		if(digit > eDigit)
			return;

	//If current digit for processing is 0, stop this branch
	if(currentNode != 0)
	     generateNumbers(10 * number + (currentNode-1), currentNode - 1, digit + 1);
		
	//If current digit for processing is 9, stop this branch
	if(currentNode != 9)
	    generateNumbers(10 * number + (currentNode + 1), currentNode + 1, digit + 1);
    }
}

Given input range limits: low and high (both inclusive).
Assume that you are generating numbers of length, say N.

Have a driver function that sets the value of the first number, first 'low' upto 'high'. then call a recursive function that does +1 and -1 to the previous value.
Code here [tested]:

#include<stdio.h>
#include<stdlib.h>

#define N 4

int low = 3;
int high = 6;

void spl_number( int a[], int pos )
{
   if( pos == N )
   {
      printf("\n");
      for( int i=0; i< N; i++ )
         printf("%d ",a[i]);
   }
   else
   {
          if( a[pos-1]-1 >= low )
          {
              a[pos] = a[pos-1] - 1;
              spl_number(a,pos+1);
          }
          if( a[pos-1]+1 <= high )
          {
              a[pos] = a[pos-1] + 1;
              spl_number(a,pos+1);
          }
   } // end else

} // end spl_number

void driver(int a[])
{
   for( int num=low; num<= high; num++ )
   {
       a[0]=num;
       spl_number(a,1);
   }
}
int main()
{
    int a[N] = { 0 };
    
    driver(a);

    return 0;
}

Range can be easily added.

public class SpecialNumber {

static String mainData = "0123456789";
public static void main(String[] args) {
printSpecialNo("","0123456789",3);
}

private static void printSpecialNo(String res, String data, int n) {
if(n==0) {
//print
System.out.println(res);
return;
}
for(int i=0;i<data.length();i++)
printSpecialNo(res+data.charAt(i), getData(data,i), n-1);
}

private static String getData(String data, int i) {
String modifiedData="";
int b = Integer.parseInt(data.charAt(i)+"");
for(int j=0;j<mainData.length();j++) {
int a = Integer.parseInt(mainData.charAt(j)+"");

if(Math.abs(a-b)==1)
modifiedData+=Integer.toString(a);
}
return modifiedData;
}

}

The problem becomes much more tractable if the special no. is treated as a string.
The recursive logic goes something like this:
for every number n in the given range:
spl_no_str = n + spl_no_str(n-1);
and
spl_no_str = n + spl_no_str(n+1);

static void printRange(int a, int b)
	{

		int n = b-a + 1;
		
		//loop for length of string
		for(int i = 2; i<=n ; i++)
		{
			// loop for starting digit of spl no.
			for(int j = a ; j<=b ; j++)
			{
				
				specialNo(j,"", a,b, i);
				
			}
		

		}

	}

	static void specialNo(int n, String s, int a, int b, int l)
	{

		if(s.length() <=l)
		{
		    	s = s + n;
	
			if(s.length() == l)
			{	
				System.out.println(s);
				
			}
				if(n+1<=b)
				specialNo( n+1, s, a, b, l);
				if(n-1>=a)
				specialNo( n-1, s, a, b, l);
		}
	
	}