Jumping Numbers Python

PROGRAM TO PRINT ALL JUMPING NUMBERS SMALLER THAN OR EQUAL TO A GIVEN VALUE


class Queue:
    def __init__(self):
        self.lst = []
  
    def is_empty(self):
        return self.lst == []
  
    def enqueue(self, elem):
        self.lst.append(elem)
  
    def dequeue(self):
        return self.lst.pop(0)
  
# Prints all jumping numbers smaller than or equal to
# x starting with 'num'. It mainly does BFS starting
# from 'num'.
def bfs(x, num):
  
    # Create a queue and enqueue i to it
    q = Queue()
    q.enqueue(num)
  
    # Do BFS starting from 1
    while (not q.is_empty()):
        num = q.dequeue()
  
        if num<= x:
            print(str(num), end =' ')
            last_dig = num % 10
  
            # If last digit is 0, append next digit only
            if last_dig == 0:
                q.enqueue((num * 10) + (last_dig + 1))
  
            # If last digit is 9, append previous digit
            # only
            elif last_dig == 9:
                q.enqueue((num * 10) + (last_dig - 1))
  
            # If last digit is neighter 0 nor 9, append
            # both previous digit and next digit
            else:
                q.enqueue((num * 10) + (last_dig - 1))
                q.enqueue((num * 10) + (last_dig + 1))
  
# Prints all jumping numbers smaller than or equal to
# a positive number x
def printJumping(x):
    print (str(0), end =' ')
    for i in range(1, 10):
        bfs(x, i)
  
# Driver Program ( Change value of x as desired )
x = 40
printJumping(x)


OUTPUT
0 1 10 12 2 21 23 3 32 34 4 5 6 7 8 9

Comments

Post a Comment

Popular posts from this blog

Facing the sun Java

PROGRAM TO FIND THE NUMBER OF BUILDINGS FACING THE SUN class Test {      // Returns count buildings that can see sunlight      static int countBuildings( int arr[], int n)      {          // Initialuze result  (Note that first building          // always sees sunlight)          int count = 1 ;                   // Start traversing element          int curr_max = arr[ 0 ];          for ( int i= 1 ; i<n; i++)          {              // If curr_element is maximum,              // update maximum and increment count              if (arr[i] > curr_max)              {                  count++;                  curr_max=arr[i];              }          }                   return count;      }              // Driver method      public static void main(String[] args)       {          int arr[] = { 7 , 4 , 8 , 2 , 9 };                      System.out.println(countBuildings(arr, arr.length));                  } } OUTPUT 3 CREDITS:  https://www.geeksforgeeks.org/number-buildings
Read more

Snake and Ladder Problem Python

PROGRAM TO SOLVE SNAKE AND LADDER PROBLEM class QueueEntry( object ):      def __init__( self , v = 0 , dist = 0 ):          self .v = v          self .dist = dist     '''This function returns minimum number of dice throws required to. Reach last cell  from 0'th cell in a snake and ladder game. move[] is an array of size N where N is  no. of cells on board. If there is no  snake or ladder from cell i, then move[i]  is -1. Otherwise move[i] contains cell to which snake or ladder at i takes to.''' def getMinDiceThrows(move, N):              # The graph has N vertices. Mark all      # the vertices as not visited      visited = [ False ] * N          # Create a queue for BFS      queue = []          # Mark the node 0 as visited and enqueue it      visited[ 0 ] = True          # Distance of 0't vertex is also 0      # Enqueue 0'th vertex      queue.append(QueueEntry( 0 , 0 ))          # Do a BFS starting from vertex at index 0      qe = QueueE
Read more

Add two numbers represented by linked lists Java

PROGRAM TO ADD TWO NUMBERS REPRESENTED BY LINKED LISTS class LinkedList {        static Node head1, head2;        static class Node {            int data;          Node next;            Node( int d)          {              data = d;              next = null ;          }      }        /* Adds contents of two linked lists and return the head node of resultant list */      Node addTwoLists(Node first, Node second)      {          // res is head node of the resultant list          Node res = null ;          Node prev = null ;          Node temp = null ;          int carry = 0 , sum;            // while both lists exist          while (first != null || second != null ) {              // Calculate value of next              // digit in resultant list.              // The next digit is sum              // of following things              // (i)  Carry              // (ii) Next digit of first              // list (if there is a next digit)              // (ii) Next digit of second    
Read more