CareerCup

public int stepping(input) {
int count=0, toplimit=10, bottomlimit=1, status=0;
int temp=input;
while (temp>1) {
toplimit*=10;
bottomlimit*=10;
temp--; }
int active=bottomlimit;
while(active<toplimit) {
int k=0;
for(int i=1;i<input;i++) {
temp1=active%10;
active-=temp1;
active/=10;
temp2=active%10;
if(temp1>temp2){
if(temp1-temp2>1){
status++;
}}
if(temp2>temp1){
if(temp2-temp1>1){
status++;
}}
if(status>0) {
count++; }
status=0;
active++; }
int total=toplimit-bottomlimit;
int result=total-active;
return result;
}
Hope it is okey.

#include <bits/stdc++.h>

using namespace std;
int main()
{
    int n;
    cin>>n;
    
    int i;
    int j;
    int a;
    int b;
    int num;
    int c;
    int stepping;
    
    stepping = 0;
    c = 0;
    num = n;
    while(num!=0) {
        num = num/10;
        c++;
    }
    
    for(i = 1; i <= n; i++) {
        
        num = i;
        int arr[c];
        a = 0;
        
        while(num!=0) {
            arr[a] = num%10;
            num = num/10;
            a++;
        }
        
        if(arr[a-1]==0){
            break;
        }
        
        int count;
        count = 1;
        
        for(j = 0; j < a-1; j++) {
            if((abs(arr[j]-arr[j+1]))==1) {
                count++;
            }
        }
        
        if((a==1)||(count==a)) {
            stepping++;
        }
    }
    
    cout<<stepping<<"\n";
    return 0;

}

#include <bits/stdc++.h>

using namespace std;
int main()
{
    int n;
    cin>>n;
    
    int i;
    int j;
    int a;
    int b;
    int num;
    int c;
    int stepping;
    
    stepping = 0;
    c = 0;
    num = n;
    while(num!=0) {
        num = num/10;
        c++;
    }
    
    for(i = 1; i <= n; i++) {
        
        num = i;
        int arr[c];
        a = 0;
        
        while(num!=0) {
            arr[a] = num%10;
            num = num/10;
            a++;
        }
        
        if(arr[a-1]==0){
            break;
        }
        
        int count;
        count = 1;
        
        for(j = 0; j < a-1; j++) {
            if((abs(arr[j]-arr[j+1]))==1) {
                count++;
            }
        }
        
        if((a==1)||(count==a)) {
            stepping++;
        }
    }
    
    cout<<stepping<<"\n";
    return 0;
}

uint64_t count_stepping_numbers(int N) {
	uint64_t arr[2][12];
	for(int i = 0; i < 12; i++) { arr[0][i] = 0; arr[1][j] = 0; }
	uint64_t sum = 0;
	for(int i = 2; i <= 10; i++) { arr[0][i] = 1; sum++;}
	for(int i = 1; i < N; i++) {
		sum = 0;
		for(int j = 1; j <= 10; j++) {
			arr[i & 1][j] = arr[ (i & 1) ^ 1 ][j - 1] + arr[(i & 1) ^ 1][j + 1];
			sum += arr[i & 1][j];
		}
	}
	return sum;
}

def step_num(digits, choices, result):
    if digits == 0:
        print result
    else:
        for choice in choices:
            next_choices = list()
            if choice + 1 < 10:
                next_choices.append(choice + 1)
            if choice - 1 > -1:
                next_choices.append(choice - 1)
            step_num(digits-1, next_choices, result + str(choice))


initial_choices = [1, 2, 3, 4, 5, 6, 7, 8, 9]
step_num(2, initial_choices, "")

def find(so_far,last,digit):
    if digit==1:
        ans=[]
        if last>0:
            ans.append(so_far+str(last-1))
        if last<9:
            ans.append(so_far+str(last+1))
        return ans
    
    a=b=[]
    if last>0:
        a=find(so_far+str(last-1),last-1,digit-1)
    if last<9:
        b=find(so_far+str(last+1),last+1,digit-1)
    return a+b

def func(n):
    ans=[]
    for i in range(1,10):
        ans=ans+find(str(i),i,n-1)
    return ans

print(func(3))

import java.io.*;
public class SteppingNumber
{
    int n;
    public SteppingNumber()throws IOException
    {
        System.out.print("Enter the number of digits:");
        n=Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
    }
    public void get()
    {
        String s;
        long count=0;
        if (n==1)
        count=10;//considering that 0 is a stepping number
        else
        for(long i=(long)Math.pow(10,(n-1)),max=i*10,flag=0;i<max;i++)
        {
            s=String.valueOf(i);
            for(int j=0;j<n-1 && flag==0;j++)
            if(Math.abs(Integer.parseInt(s.substring(j,j+1))-Integer.parseInt(s.substring(j+1,j+2)))!=1)
            flag=1;
            if(flag==0)
            count+=1;
            else
            flag=0;
        }
        System.out.println(count);
    }
    public static void main(String a[])throws IOException
    {
        SteppingNumber psi=new SteppingNumber();
        psi.get();
    }
}

n = 890
steps = 1
step_num, n = n%10, n//10
while n > 9:
    if abs(step_num - n%10) == 1:
        steps += 1
        step_num = n%10
    n //= 10
if n != 0 and abs(step_num - n) == 1:
        step_num += 1
if n == 0:
    print '0'
print steps

The solution is:


Stepping(n) = Stepping(n-1)*2 +2 where
Stepping(2) = 18
Stepping for n<2 = 0

It can be solve in O(N) by using the formula
Stepping(0) = 0
Stepping(1)=0
Stepping(2)=18
Stepping(N) = ( Stepping(N-1)*2 ) - 2

package com.math.util;

import java.util.ArrayList;
import java.util.List;

public class SteppingNumber {
	public static void main(String[] args) {
		SteppingNumber steppingNumber = new SteppingNumber(); 
		System.out.println("SteppingNumber" + steppingNumber.getSteppingNumber());
	}

	public List<Integer> getSteppingNumber() {
		List<Integer> steppingNumberList = new ArrayList<Integer>();
		int a, b, c, temp = 0;
		for (int i = 100; i <= 999; i++) {
			c = i % 10;
			temp = i / 10;
			a = temp / 10;
			b = temp % 10;
			if ((Math.abs(Math.subtractExact(a, b))) == (Math.abs(Math.subtractExact(b, c)))) {
				steppingNumberList.add(i);
			}
		}

		return steppingNumberList;
	}
}