N Queen problem

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

CODE

solveNQUtil(board, 0);
bool solveNQUtil(int board[N][N], int col)
{
    if (col >= N)
        return true;
 
    for (int i = 0; i < N; i++)
    {
        if ( isSafe(board, i, col) )
        {
            board[i][col] = 1;
 
            if ( solveNQUtil(board, col + 1) == true )
                return true;
 
            board[i][col] = 0; // BACKTRACK
        }
    }
    return false;
}

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;
 
    /* Check this row on left side for attacking queens*/
    for (i = 0; i < col; i++)
    {
        if (board[row][i])
            return false;
    }
 
    /* Check upper diagonal on left side */
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
            return false;
    }
 
    /* Check lower diagonal on left side */
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
    {
        if (board[i][j])
            return false;
    }
 
    return true;
}

Implement Stack using Queues

push(s,  x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).

pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more movement of all elements from q2 to q1.
CODE

struct stack
{
  struct sNode *queue1;
  struct sNode *queue2;
};

void push(struct stack *s, int x)
{
  enqueue(&s-> queue1, x);
}

int pop(struct stack *s)
{
   int x; 
  
   if(s-> queue1== NULL && s->queue2== NULL)
   {
      printf("Stack is empty");
      exit(0);
   }

   while(queue1.getSize() != 1 )
   {
       x = queue1.dequeue();
       queue2.enqueue(x);
   }
   int value = queue1.dequeue();
   
   while( ! queue2.isEmpty() )
   {
       queue1.enqueue(queue2.dequeue() );
   }
   return value;
}

Stack  can also be implemented using one user Queue and one Function Call Queue (Recursion).
push(x)
1) Enqueue x to Queue1.

Pop():
1) If queue1 is empty then error.
2) If queue1 has only one element then return it.
3) Recursively pop everything from the queue1, store the popped item
in a variable res,  push the res back to queue1 and return res

struct stack
{
  struct sNode *queue1;
};

void push(struct stack *s, int x)
{
  enqueue(&s-> queue1, x);
}
  
int pop(struct stack *s)
{
   int x, res; 
  
   if(q->queue1== NULL)
   {
     printf("Stack is empty");
     exit(0);
   }
   else if(q->queue1->next == NULL)
   {
      return dequeue(&q->queue1);
   }
   else
   {
      x = dequeue (&q->queue1);
      res = pop(q);
      enqueue (&q->queue1, x);
  
      return res;
   }
}

Implement Queue using Stacks

enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.

CODE

struct queue
{
  struct sNode *stack1;
};

/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
   push(&q->stack1, x);
}
  
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
   int x; 
  
   /* If both stacks are empty then error */
   if(q->stack1 == NULL && q->stack2 == NULL)
   {
      printf("Q is empty");
      getchar();
      exit(0);
   }
 
   /* Move elements from satck1 to stack 2 only if stack2 is empty */
   if(q->stack2 == NULL)
   {
     while(q->stack1 != NULL)
     {
        x = pop(&q->stack1);
        push(&q->stack2, x);
     }
   } 
 
   x = pop(&q->stack2);
   return x;
}

Queue can also be implemented using one user stack and one Function Call Stack (Recursion).
enQueue(x)
1) Push x to stack1.

deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item in a variable res,  push the res back to stack1 and return res

struct queue
{
  struct sNode *stack1;
};

void enQueue(struct queue *q, int x)
{
  push(&q->stack1, x);
}
  
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
   int x, res; 
  
   if(q->stack1 == NULL)
   {
     printf("Q is empty");
     getchar();
     exit(0);
   }
   else if(q->stack1->next == NULL)
   {
      return pop(&q->stack1);
   }
   else
   {
      /* pop an item from the stack1 */
      x = pop(&q->stack1);
  
      /* store the last dequeued item */
      res = deQueue(q);
  
      /* push everything back to stack1 */
      push(&q->stack1, x);
  
      return res;
   }
}

Count Inversions in an array

int _mergeSort(int arr[], int temp[], int left, int right)
{
  int mid, inv_count = 0;
  if (right > left)
  {
     mid = (right + left)/2;
  
     inv_count  = _mergeSort(arr, temp, left, mid);
     inv_count += _mergeSort(arr, temp, mid+1, right);
     inv_count += merge(arr, temp, left, mid+1, right);
  }
  return inv_count;
}
  
int merge(int arr[], int temp[], int left, int mid, int right)
{
  int i, j, k;
  int inv_count = 0;
  
  i = left;
  j = mid; 
  k = left;
  while ((i <= mid - 1) && (j <= right))
  {
    if (arr[i] <= arr[j])
    {
      temp[k++] = arr[i++];
    }
    else
    {
      temp[k++] = arr[j++];
    }
      inv_count += (mid - i);
    }
  }
  
  while (i <= mid - 1)
    temp[k++] = arr[i++];
  
  while (j <= right)
    temp[k++] = arr[j++];
  
  for (i=left; i <= right; i++)
    arr[i] = temp[i];
  
  return inv_count;
}

Build Lowest Number by Removing n digits from a given number

void buildLowestNumberRec(string str, int n, string &res)
{
   if (n == 0)
   { 
      res.append(str);
      return;
    }
    int len = str.length();
    if (len <= n)
        return;
     int minIndex = 0;
     for (int i = 1; i<=n ; i++)
        if (str[i] < str[minIndex])
            minIndex = i;
     res.push_back(str[minIndex]);
     string new_str = str.substr(minIndex+1, len-minIndex);
     buildLowestNumberRec(new_str, n-minIndex, res);
 }

How to print maximum number of A’s using given four keys

int findoptimal(int N)
{
    // The optimal string length is N when N is smaller than 7
    if (N <= 6)
        return N;
 
    // Initialize result
    int max = 0;
 
    // TRY ALL POSSIBLE BREAK-POINTS
    // For any keystroke N, we need to loop from N-3 keystrokes
    // back to 1 keystroke to find a breakpoint 'b' after which we
    // will have Ctrl-A, Ctrl-C and then only Ctrl-V all the way.
    int b;
    for (b=N-3; b>=1; b--)
    {
            // If the breakpoint is at b'th keystroke
            int curr = (N-b-1)*findoptimal(b);
            if (curr > max)
                max = curr;
     }
     return max;
}

Explanation
For N = 7
Case1
B = n-3 = 4
AAAA Ctrl-A Ctrl-C Ctrl-V = 8;    n-b-1 = 7-4-1 = 2 * findoptimal(4) = 2*4 = 8

Case2
B = 3
AAA Ctrl-A Ctrl-C Ctrl-V Ctrl-V= 9;  n-b-1 = 7-3-1 = 3* findoptimal(3) = 3*3 = 9

Case3
B = 2
AA Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V =  8; n-b-1 = 7-2-1 = 4* findoptimal(2) = 4*2 = 8

Case4
B = 1
A Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V = 5; n-b-1 = 7-1-1 = 5* findoptimal(1) = 5*1 = 5

For N = 10
B = n-3 = 7

n-b-1 = 10-7-1 = 2*findoptimal(7)

Minimum number of jumps to reach end

/*
 * We use "last" to keep track of the maximum distance that has been reached
 * by using the minimum steps "ret", whereas "curr" is the maximum distance
 * that can be reached by using "ret+1" steps. Thus,
 * curr = max(i+A[i]) where 0 <= i <= last.
 */
    
   int jump(int A[], int n) {
        int ret = 0;
        int last = 0;
        int curr = 0;
        for (int i = 0; i < n; ++i) {
            if (i > last) {
                last = curr;
                ++ret;
            }
            curr = max(curr, i+A[i]);
        }

        return ret;
    }

Counting integers in a string

String s = "abcd123";
    int counter = 0;
    for(char c : s.toCharArray()) 
    {
        if( c >= '0' && c<= '9') 
        {
            ++counter;
        }
    }

OR

String s = "abcd123";
int count = 0;
for (int i = 0, len = s.length(); i < len; i++) 
{
    if (Character.isDigit(s.charAt(i))) 
    {
        count++;
    }
}

Square of a number without using *, / ,+and pow()

If n is even, it can be written as

  n = 2*x 
  n2 = (2*x)2 = 4*x2

If n is odd, it can be written as

  n = 2*x + 1
  n2 = (2*x + 1)2 = 4*x2 + 4*x + 1

square(n) = 0 if n == 0
  if n is even 
     square(n) = 4*square(n/2) 
  if n is odd
     square(n) = 4*square(floor(n/2)) + 4*floor(n/2) + 1

Examples
square(6) = 4*square(3)
square(3) = 4*(square(1)) + 4*1 + 1 = 9
square(7) = 4*square(3) + 4*3 + 1 = 4*9 + 4*3 + 1 = 49

CODE

int square(int n)
{
    // Base case
    if (n==0) return 0;
 
    // Handle negative number
    if (n < 0) n = -n;
 
    // Get floor(n/2) using right shift
    int x = n>>1;
 
    // If n is odd
    if (n&1)
        return ((square(x)<<2) + (x<<2) + 1);
    else // If n is even
        return (square(x)<<2);

Find word in dictionary

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Answer

public int ladderLength(String start, String end, HashSet<String> dict) {
    if (dict.size() == 0)
        return 0;
 
    dict.add(end);
 
    LinkedList<String> wordQueue = new LinkedList<String>();
    LinkedList<Integer> distanceQueue = new LinkedList<Integer>();
 
    wordQueue.add(start);
    distanceQueue.add(1);
 
    //track the shortest path
    int result = Integer.MAX_VALUE;
    while (!wordQueue.isEmpty()) {
        String currWord = wordQueue.pop();
        Integer currDistance = distanceQueue.pop();
 
        if (currWord.equals(end)) {
            result = Math.min(result, currDistance);
        }
 
        for (int i = 0; i < currWord.length(); i++) {
            char[] currCharArr = currWord.toCharArray();
            for (char c = 'a'; c <= 'z'; c++) {
                currCharArr[i] = c;
 
                String newWord = new String(currCharArr);
                if (dict.contains(newWord)) {
                    wordQueue.add(newWord);
                    distanceQueue.add(currDistance + 1);
                    dict.remove(newWord);
                }
            }
        }
    }
 
    if (result < Integer.MAX_VALUE)
        return result;
    else
        return 0;
}