Find out minimum operations required

There are three operations given:  

     op1 => divid by 3

     op2 => divide by 2

     op3 => subtract 1

Find minimal no. of operation required to convert a given no. to 1.

E.g.: To convert 10 to 1 minimum "3" operations are required as explained below

10 -> op3 = 9

9   -> op1 = 3

3   -> op1 = 1

Approach 1: Brute force

This problem can be solved using recursion. Try every possible operation till the number becomes equal to 1 and find minimum operations out of these.

class Solution {
   public static int noOfOperations(int n, int cur_op_count, int min_op_count) {

        if (cur_op_count >= min_op_count)
            return cur_op_count;  // this indicate a invalid path(not an optimal) so return
        if (n == 1) return cur_op_count;

        int size1 = Integer.MAX_VALUE;
        int size2 = Integer.MAX_VALUE;
        int size3 = Integer.MAX_VALUE;

        cur_op_count = cur_op_count + 1;

        if (n % 3 == 0)
            size1 = noOfOperations(n / 3, cur_op_count, min_op_count);
        min_op_count = Math.min(min_op_count, size1);

        if (n % 2 == 0)
            size2 = noOfOperations(n / 2, cur_op_count, min_op_count);
        min_op_count = Math.min(min_op_count, size2);

        size3 = noOfOperations(n - 1, cur_op_count, min_op_count);
        return Math.min(Math.min(size1, size2), size3);
    }

    public static void main(String[] args) {
        System.out.println(noOfOperations(22, 0, Integer.MAX_VALUE));
    }
}

Approach 2: Dynamic Programming

In brute force approach we are not storing the results so recursion will try to solve same subproblem every time. Add a temporary storage to hold the result of earlier solutions and use the same for next results.

Code below demonstrate approach 2 implementation.

class Solution {

    public static int minOperations(int input, int[] operations){
        if(input <= 1)
            return 0;
        if(operations[input] != -1)
            return operations[input];

        int divBy3=Integer.MAX_VALUE, divBy2 = Integer.MAX_VALUE;

        if(input % 3 == 0){
            divBy3 = minOperations(input/3, operations) + 1;
        }

        if(input % 2 == 0){
            divBy2 = minOperations(input/2, operations) + 1;
        }
        int sub1 = minOperations(input - 1, operations) + 1;

        int min = Math.min(Math.min(divBy3, divBy2), sub1);
        operations[input] = min;
        return min;
    }

    public static void main(String[] args) {
        int input = 11;
        int[] operations = new int[input+1];
        for(int i=0; i < operations.length; i++) operations[i] = -1;
        operations[0] = 0;
        operations[1] = 0;
        System.out.println("Min Operations : " + minOperations(input, operations));
    }
}

Comments are welcome.

Find out all pairs having difference equals to 'K' in sorted array

We have given a sorted array of integer. Need to find out all pair of element having difference as ‘k'.

Approach 1 : Brute force
We can start with first element of array and subtract it with every other number from array and check the diff. Repeat this for rest all elements. Complexity O(N^2)

Approach 2 : Binary Search
As the array elements are sorted we can use binary search to search the matching element. E.g. take first element from array, and search for element equals to "k - first element". 
This we can repeat for all the elements in the array. Complexity O(NlogN) 

Approach 3 : Use Set/HashMap
If we are allowed to use additional space we can add elements HashSet or HashMap as key one by one and check before adding if element equal to "k - element to be added" exists in set. Complexity O(N)

Approach 4: Increment or decrement indexes based on difference:
Use two indices out of which one starts at beginning and one starts at first index plus one. As the array is sorted, you just want to check if current diff is less than or greater than k (key), based on the result increment or decrement indices. If we found match update both indices. Complexity O(N)

Below solution implements approach 4. This solution will not display duplicate pairs if we have duplicate numbers.

class Solution {
    public static void findPairHavingDiff(int[] numbers, int k){
        if(numbers.length > 0){
            int start = 0;
            int end = 1;
            while(end < numbers.length){
                int diff = numbers[end] - numbers[start] ;
                if(diff == k) {
                    System.out.println("Found Pair : " + numbers[start] + " & " + numbers[end]);
                    start++;
                    end++;
                }
                else if(diff < k) end++;
                else if(diff > k) start++;
            }
        }
        else System.out.println("None found");
    }

    public static void main(String[] args) {
        int[] input = {-1, 2, 3, 4, 5, 6, 7, 8, 10 };
        findPairHavingDiff(input, 9);
    }
}

//Output of the above solution is
Found Pair : -1 & 8

Reverse an array without affecting special characters

Given a string, that contains special character together with alphabets (‘a’ to ‘z’ and ‘A’ to ‘Z’), reverse the string in a way that special characters are not affected. e.g.

    Input:   str = "a,b$c"
    Output:  str = "c,b$a"
    Note that $ and , are not moved anywhere.  
    Only subsequence "abc" is reversed

    Input:   str = "Ab,c,de!$"
    Output:  str = "ed,c,bA!$"
     

Approach 1

 
public class Solution {  
   public static void main(String[] args) {  
     System.out.println(reverseString("man ish#"));  
   }  
   /**  
    * Reverse string with maintaining special character in place  
    *  
    * Algorithm:  
    * 1. create temporary array  
    * 2. copy all character from original array excluding special character  
    * 3. reverse the temporary array  
    * 4. start copying temporary array into original if element is an alphabetic character  
    * @param input  
    * @return  
    */  
   public static String reverseString(String input) {  
     char[] inputArr = input.toCharArray();  
     char[] tempArr = new char[input.length()];  
     int i=0;  
     int j=0;  
     for (char ch:inputArr){  
       if(Character.isAlphabetic(ch)){  
         tempArr[i] = ch;  
         i++;  
       }  
     }  
     i--;  
     while(j<i){  
       char temp = tempArr[i];  
       tempArr[i]= tempArr[j];  
       tempArr[j]=temp;  
       j++;  
       i--;  
     }  
     for(i=0,j=0;i<input.length();i++){  
       if(Character.isAlphabetic(inputArr[i])){  
         inputArr[i]= tempArr[j++];  
       }  
     }  
     return new String(inputArr);  
   }  
 }  

Approach 2

 
public class Solution {  
   public static void main(String[] args) {  
     System.out.println(reverseString("man ish#"));  
   }  
   /**  
    * Reverse a string with maintaining special character position.  
    * Algorithm :  
    * 1) Let input string be 'str[]' and length of string be 'n'  
    * 2) l = 0, r = n-1  
    * 3) While l is smaller than r, do following  
    * a) If str[l] is not an alphabetic character, do l++  
    * b) Else If str[r] is not an alphabetic character, do r--  
    * c) Else swap str[l] and str[r]  
    *  
    * @param input : Input string  
    * @return reverse string  
    */  
   public static String reverseString(String input) {  
     char[] inputArr = input.toCharArray();  
     int l = 0;  
     int r = inputArr.length - 1;  
     while (l < r) {  
       if (!Character.isAlphabetic(inputArr[l])) {  
         l++;  
       } else if (!Character.isAlphabetic(inputArr[r])) {  
         r--;  
       } else {  
         char tempChar = inputArr[l];  
         inputArr[l] = inputArr[r];  
         inputArr[r] = tempChar;  
         l++;  
         r--;  
       }  
     }  
     return new String(inputArr);  
   }  
 }  

Find out all pair of element having sum as ‘k' in given sorted array

We have given a sorted array of integer. Need to find out all pair of element having sum as ‘k'.

Approach 1 : Brute force
We can start with first element of array and add it with every other number from array and check the sum. Repeat this for rest all elements. Complexity O(N^2)
This brute force approach can be slightly improved by adding the elements from the current index + 1 to the index where sum is greater than k (key).

Approach 2 : Binary Search
As the array elements are sorted we can use binary search to search the matching element. E.g. take first element from array, and search for element equals to "k + first element".
This we can repeat for all the elements in the array. Complexity O(NlogN)

Approach 3 : Use Set/HashMap
If we are allowed to use additional space we can add elements HashSet or HashMap as key one by one and check before adding if element equal to "k + element to be added in set" exists in set. Complexity O(N)

Approach 4: Increment or decrement indexes based on sum:
Use two indices out of which one starts at beginning and one starts at end. As the array is sorted, you just want to check if current sum is less than or greater than k (key), based on the result increment or decrement end index. If we found match update both indices. Complexity O(N)

Below solution implements approach 4. This approach does not display duplicate pairs if we have duplicate elements.

class Solution {
    public static void findPair(int[] numbers, int k){
        if(numbers.length > 0){
            //get first & last index from the sorted array
            int start = 0;
            int end = numbers.length - 1;
            while(start < end){
                int sum = numbers[start] + numbers[end];
                if(sum == k) {
                    System.out.println("Found Pair : " + numbers[start] + " & " + numbers[end]);
                    start++;
                    end--;
                }
                else if(sum < k) start++;
                else if(sum > k) end--;
            }
        }
        else System.out.println("None found");
    }

    public static void main(String[] args) {
        int[] input = {0, 2, 3, 5, 6, 8, 12, 15, 18 };
        findPair(input, 18);
    }
}

//Output of the above solution is
Found Pair : 0 & 18
Found Pair : 3 & 15
Found Pair : 6 & 12

Finding duplicate from array having element from 0 to n-2.

An array contains n numbers ranging from 0 to n-2. There is exactly one number duplicated in the array. How do you find the duplicated number? For example, if an array with length 5 contains numbers {0, 2, 1, 3, 2}, the duplicated number is 2. Solution:

class Solution {
    public static int findDuplicate(int numbers[]) {
        int length = numbers.length;
        int sum1 = 0;
        for (int number : numbers) {
            if (number < 0 || number > length - 2)
                throw new IllegalArgumentException("Invalid numbers.");
            sum1 += number;
        }
        // Calcualate the sum of number from 1 to n as n(n-1)/2  
        int sum2 = ((length - 1) * (length - 2)) >> 1;
        return sum1 - sum2;
    }
    public static void main(String[] args) {
        int input[] = {0, 2, 1, 3, 2};
        System.out.println("Duplicate Number : " + findDuplicate(input));
    }
}

//Output of above code will be 
Duplicate Number : 2