Given a number, using the same set of digits of it to compose the smallest number which is greater than the input

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”. 

examples:
input: 1111
output: not possible

inout: 1234
output: 1243

input: 12345765
output: 12346557


In order to make a number greater but as small as possible, we need to achieve couple things: 1) try to change the least significant digits as possible; 2) in order make number bigger, we need to swap a smaller digit with a bigger digit on its right; 3) once we accomplish goal 1 and 2, we need to further make the number smaller. 

Here is the algorithm:
1. going from the right side of the number, find the first digit with index i which is smaller than the digit on its right
2. do binary search from i+1 to number.length-1 to find the smallest digit which is bigger than the digit at index i.
3. swap digits at index i and digit find in step 2.
3. reverse all of the digits from i+1 to number.length-1.


//digits are sorted descending numbers
public static int binarySearch(int[] digits, int start, int end, int v){
    while(start<end-1){
        int mid = (start+end)>>>1;
        if(digits[mid]>=v)
            start = mid;
        else
            end = mid;  
    }
    return digits[end] > v? end : start;
}

public static int swap(int[] digits, int t1, int t2){
  int d = digits[t1]; digits[t1] = digits[t2]; digits[t2] = d;
}

public static void reverse(int[] digits, int start, int end){
  while(start<end)
      swap(digits, start++, end--);
}

public static void findNGE(int number){
 int len = 0, temp = number;
 while(temp>0){
     len++;  temp = temp/10;
 }
 int[] digits = new int[len];
 temp = number;
 while(temp>0){
     digits[--len] = temp%10; temp = temp/10;
 }

 int end = digits.length - 1;
 while(end-1>=0 && digits[end]<=digits[end-1])
     end--;

 if(end==0)
   System.out.println("not possible");
 else{
   //binary search from end and digits.length -1
   //to find the smallest digit larger than digits[end-1]
   int target = binarySearch(digits, end, digits.length-1);
   swap(digits, target, end-1);
   reverse(digits, end, digits.length-1);
 
   int result = 0;
   for(int d : digits)
       result = d + result*10;

   System.out.println(result);
 }
}

Calculate maximum qaz value of a number array

This problem can be found at careercup site: http://www.careercup.com/question?id=5649103830646784

Qaz value for each element in a number array is defined as the number of elements whose both value and index are larger than current element. Maximum qaz value of array is the maximum of the qaz values.

Many answers from careercup site use mergeSort algorithm, which is pretty awesome. Since the time complexity requirement is O(nlgn), I assume other sorting approach will work too. Here I use order statistics binary search tree. To better understand order statistics binary search tree, please see my blog here: http://blueocean-penn.blogspot.com/2015/01/order-statistics-binary-search-tree.html

What is the caveat of the following implementation? I will leave it to readers. ;)

Calculate Qaz using binary search tree.

public static class QNode{

int val;

int size;

QNode left, right;

QNode(int v, int s){val = v; size = s;}

//time complexity O(n), n is the tree height 

void insert(int target){

size++;

if(target<=this.val){//smaller or equal goes left

if(this.left==null)

this.left = new QNode(target, 1);

else

this.left.insert(target);

}else{

if(this.right==null)

this.right = new QNode(target, 1);

else

this.right.insert(target);

}

}

//time complexity O(n), n is the tree height 

int findIndexFor(int value){

int passed = 0;

QNode curr = this;

while(curr!=null){

if(curr.val == value){

return (curr.left==null?0:curr.left.size) + passed;

}else if(curr.val > value){

curr = curr.left;

}else{

passed += (curr.left==null?0:curr.left.size) + 1;

curr = curr.right;

}

}

return -1;

}

}

public static int maxQAZ(int[] nums){

assert(nums != null);

int len = nums.length;

QNode root = new QNode(nums[len-1], 1);

int max = 0;

for(int i=len-2; i>=0; i--){

root.insert(nums[i]);

max = Math.max(max, i- root.findIndexFor(nums[i]));

}

return max;

}

An alternative solution is to modify merge sort to calculate qaz for an array.

//find QAZ using merge sort

public static class Qaz{

int v; int qaz;

public Qaz(int v){this.v = v;}

public String toString(){

return v + "-" + qaz;

}

}

public static void qazBymergeSort(int[] nums){

int len = nums.length;

Qaz[] objs = new Qaz[len];

for(int i = 0; i< len; i++){

objs[i] = new Qaz(nums[i]);

}

mergeSort(objs, 0, len-1);

System.out.println(Arrays.toString(objs));

}

public static void mergeSort(Qaz[] nums, int start, int end){

if(start>=end)

return;

int mid = (start+end)>>>1;

mergeSort(nums, start, mid);

mergeSort(nums, mid+1, end);

merge(nums, start, mid, end);

}

public static void merge(Qaz[] nums, int start, int mid, int end){

Qaz[] temp = new Qaz[end-start+1];

int start2 = mid+1;

int k = temp.length-1;

int add = 0;

while(start<=mid && start2<=end){

if(nums[mid].v<nums[end].v){

temp[k--] = nums[end--];

add++;

}

else{

temp[k] = nums[mid--];

temp[k].qaz = temp[k].qaz + add;

k--;

}

}

while(start<=mid){

temp[k] = nums[mid--];

temp[k].qaz = temp[k].qaz + add;

k--;

}

while(start2<=end)

temp[k--] = nums[end--];

  System.arraycopy(temp, 0, nums, start, temp.length);

}

Find local min in list of distinct numbers

Given a list of distinct numbers, find the number is smaller than its adjacent numbers, if the number is at the start or end of the list, then this number is smaller than its neighbor only.

This problem can also extend to different problem, given a list of numbers, find the number is not bigger than its adjacent numbers, if the number is at the start or end of the list, then this number is smaller than its neighbor only.

The solution is to do binary search:

//find local min

public static int findLocalMin(int[] nums){

if(nums.length == 0)

return -1;

if(nums.length <= 2)

return 0;

int start = 0, end = nums.length -1;

while(start<end-1){

int mid = (start + end)>>>1;

if(nums[mid]<nums[mid-1] && nums[mid]<nums[mid+1]){

return mid;

}else if(nums[mid] > nums[mid-1])

end = mid;

else

start = mid;

}

if(nums[start] < nums[end])

return start;

else 

return end;

}

A question for the reader, can you figure out a solution to find local min in 2D matrix?