Finding Earnings of a Zoo Driver

Question : 

There is a zoo and there are several groups(number of groups:K) of people for tour. Each group is having different size (g1,g2,g3…gK). There is one bus with capacity C. Journey starts from a point and bus will come back to the same point. A group can only be included in the bus if all the members of the groups can be accumulated in bus. After coming back from the tour, each group in the bus will again wait in the queue at the bus-stand. Bus-driver earns a rupee for each person travelled. You have to find the earning of the bus driver after R rounds.

Example : 

Number of groups G = 4

 Group size for each group : 2 4 3 5

 Bus capacity : 7

 Number of rounds R : 4



 queue : (from front side) 2 4 3 5

 First round : 2 4 (we can’t take 3rd group as 3 members can’t be accumulated after 2 and 4.)

 queue : 3 5 2 4 (1st and 2nd group are enqueued. i.e. 2 and 4)

 Second round : 3

 queue : 5 2 4 3

 Third Round : 5 2

 queue : 4 3 5 2

 Fourth Round : 4 3

 After 4 rounds, total earning is 6+3+7+7 = 23.

Code : 

 import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created by Aniket on 2/8/14.
 */
public class ZooDriverEarningsFinder {

    int numberOfGroups;
    int[] groupSizes;
    int busCapacity;
    int noOfRounds;

    public ZooDriverEarningsFinder(int numberOfGroups, int[] groupSizes,int busCapacity,int noOfRounds){
        this.numberOfGroups = numberOfGroups;
        this.groupSizes = groupSizes;
        this.busCapacity = busCapacity;
        this.noOfRounds = noOfRounds;
    }

    public int calculateEarnings(){

        Queue<Integer> groupsQueue = new LinkedList<Integer>();
        for(int grpSize : groupSizes){
            groupsQueue.offer(grpSize);
        }

        int roundsCount = 0;
        int earnings = 0;

        while(roundsCount < noOfRounds){

            int currentCapacity = 0;

            while(currentCapacity <= busCapacity){
                int nextGrpSize = groupsQueue.peek();
                if((currentCapacity + nextGrpSize) <= busCapacity){
                    currentCapacity = currentCapacity + nextGrpSize;
                    groupsQueue.offer(groupsQueue.poll());
                }
                else {
                    //bus is full. Commence journey
                    break;
                }
            }
            //capacity is full. Add earning.
            earnings = earnings + currentCapacity;
            //increment rounds
            roundsCount++;
        }
        return earnings;
    }

    public static void main(String args[]){

        Scanner scanner = new Scanner(System.in);

        //get number of groups
        int numberOfGroups = scanner.nextInt();

       int[] groupSizes = new int[numberOfGroups];

        //get group sizes
        for(int i=0; i<numberOfGroups; i++){
            groupSizes[i] = scanner.nextInt();
        }

        int busCapacity = scanner.nextInt();

        int noOfRounds = scanner.nextInt();

        ZooDriverEarningsFinder earningsFinder = new ZooDriverEarningsFinder(numberOfGroups,groupSizes,busCapacity,noOfRounds);
        System.out.println("Total Earnings : " + earningsFinder.calculateEarnings());
    }
}

Output : 

4
2
4
3
5
7
4
Total Earnings : 23

Search an element in a sorted and pivoted array

Question : 

Link of Question : (GeeksForGeeks)
An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

Algorithm :

Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

• Input arr[] = {3, 4, 5, 1, 2}

• Element to Search = 1

1.  Find out pivot point and divide the array in two 

   sub-arrays. (pivot = 2) /*Index of 5*

2. Now call binary search for one of the two sub-arrays.

   • If element is greater than 0th element then search in left array

   • Else Search in right array (1 will go in else as 1 < 0th element(3))

3. If element is found in selected sub-array then return index 
        Else return -1.

Code : 

package Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 5/2/14
 * Time: 12:08 PM
 */
public class RotatedBinarySearcher {

    public int pivotedBinarySearch(int[] array, int no){

        int endIndex = array.length - 1;

        int pivot = findPivot(array,0,endIndex);

        System.out.println("Pivot Index : " + pivot);


        if(pivot == -1){    //Array is just sorted and not rotated
            return binarySearch(array,0,endIndex,no);
        }

        if(array[pivot] == no){
            return pivot;
        }
        else if(array[0] <= no){    //If number is greater than array[0] then it is must be left side of pivot
            return binarySearch(array,0,pivot-1,no);
        }
        else {
            return binarySearch(array,pivot+1,endIndex,no);
        }
    }


    private int findPivot(int [] array, int start, int end){

        if(start > end){
            return -1;
        }

        if(start == end){
            return start;
        }

        int mid = (start + end) / 2;

        if(mid > start && array[mid] < array[mid-1]){
            return mid - 1;
        }
        if(mid < end && array[mid] > array[mid + 1]){
            return mid;
        }

        if(array[mid] <= array[start]){
            return findPivot(array, start, mid-1);
        }
        else {  //array[mid] > array[end]
            return findPivot(array, mid + 1, end);
        }
    }

    private int binarySearch(int[] array, int start, int end, int number){

        if(start > end){
            return -1;
        }

        int mid = (end + start)/2;

        if(array[mid] == number){
            return mid;
        }

        if(number < array[mid]){
            return binarySearch(array, start, mid - 1, number);
        }
        else{
            //number > array[mid]
            return binarySearch(array, mid + 1, end, number);
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{3,4,5,1,2};
        int searchIndex = new RotatedBinarySearcher().pivotedBinarySearch(array,1);
        System.out.println("Number is at index : " + searchIndex);

    }

}

Output : 

Pivot Index : 2
Number is at index : 3