Algo practice doc.txt

## Sample algorithms logic reference

Array: 

* Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

code snippet:
	
	void leftRotate(int arr[], int d, int n)
    {
        for (int i = 0; i < d; i++)
            leftRotatebyOne(arr, n);
    }
 
    void leftRotatebyOne(int arr[], int n)
    {
        int i, temp;
        temp = arr[0];
        for (i = 0; i < n - 1; i++)
            arr[i] = arr[i + 1];
        arr[n-1] = temp;
    }


Time complexity : O(n * d) 
Auxiliary Space : O(1)


* Find the Rotation Count(index value) in Rotated Sorted array

static int countRotations(int arr[], int low,
                                       int high)
    {
	
	//low = 0;
	//high = arr.length-1
       
	   // This condition is needed to handle
        // the case when array is not rotated
        // at all
        if (high < low)
            return 0;
 
        // If there is only one element left
        if (high == low)
            return low;
 
        // Find mid
       
        int mid = low + (high - low)/2;
 
        // Check if element (mid+1) is minimum
        // element. Consider the cases like
        // {3, 4, 5, 1, 2}
        if (mid < high && arr[mid+1] < arr[mid])
            return (mid + 1);
 
        // Check if mid itself is minimum element
        if (mid > low && arr[mid] < arr[mid - 1])
            return mid;
 
        // Decide whether we need to go to left
        // half or right half
        if (arr[high] > arr[mid])
            return countRotations(arr, low, mid - 1);
 
        return countRotations(arr, mid + 1, high);
    }

Time Complexity : O(Log n) 
Auxiliary Space : O(1)


Q. Quickly find multiple left rotations of an array

// int arr[] = {1, 3, 5, 7, 9};
  //  int n = arr.length;
     
  //  int k = 2; pass any value of k for k number of rotation of original array

	static void leftRotate(int arr[],
                       int n, int k)
{
    // Print array after
    // k rotations
    for (int i = k; i < k + n; i++)
        System.out.print(arr[i % n] + " ");
}


Q. Move all zeroes to end of array

	int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
	int n = arr.length;
// output : 1 9 8 4 2 7 6 9 0 0 0 0
 static void pushZerosToEnd(int arr[], int n)
    {
        int count = 0;  // Count of non-zero elements
 
        // Traverse the array. If element encountered is
        // non-zero, then replace the element at index 'count'
        // with this element
        for (int i = 0; i < n; i++)
            if (arr[i] != 0)
                arr[count++] = arr[i]; // here count is
                                       // incremented
 
        // Now all non-zero elements have been shifted to
        // front and 'count' is set as index of first 0.
        // Make all elements 0 from count to end.
        while (count < n)
            arr[count++] = 0;
    }
	
Time Complexity: O(n) where n is number of elements in input array.
Auxiliary Space: O(1)


Q. Segregate even and odd numbers(even first followed by odd)


int arr[] = { 1, 3, 2, 4, 7,
                            6, 9, 10 };
        int n = arr.length;
		
//output : 2 4 6 10 7 1 9 3
static void arrayEvenAndOdd(
                  int arr[], int n)
    {
      
        int i = -1, j = 0;
        while (j != n) {
            if (arr[j] % 2 == 0)
            {
                i++;
      
                // Swapping even and
                // odd numbers
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
      
        // Printing segregated array
        for (int k = 0; k < n; k++)
             System.out.print(arr[k] + " ");
    }
	
Time Complexity : O(n) 
Auxiliary Space : O(1)


Q. K’th Smallest/Largest Element in Unsorted Array


Integer arr[] = new Integer[] { 12, 3, 5, 7, 19 };
int k = 2;

//output : 5
 public static int kthSmallest(Integer[] arr,
                                  int k)
    {
        // Sort the given array
        Arrays.sort(arr);
 
        // Return k'th element in
        // the sorted array
        return arr[k - 1];
    }
	
Q. 2nd largest element in an array without using built-in method like Arrays.sort()

public static int SecondLargestElement(int[] arr) {


int max = INTEGER.MIN_VALUE;

for(int i=0;i<arr.length;i++) {

	max = Math.max(max,arr[i]);
}

int second = 0;

for(int i=0;i<arr.length;i++) {
	if(arr[i] != max) {
	second = Math.max(second,arr[i]);
	
}

if (second == Integer.MIN_VALUE)
        System.out.printf("There is no second " +
                          "largest element\n");
    else
        System.out.printf("The second largest " +
                          "element is %d\n", second);
}