CODEWITHSUNDEEP
javaperformancetime-complexity
apoorva sharma
apoorva sharma

Reputation: 9

How to reduce time complexity of the code?

I have given a queue initial positions increment by 1 from 1 at the front of the line to n at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n = 8 and Person 5 bribes Person 4, the queue will look like this:1,2,3,5,4,6,7,8.

minimumbribes must print an integer representing the minimum number of bribes necessary to create the original queue, or Too chaotic if the line configuration is not possible. If no of bribes for a person exceeds to 2 then the line configuration is not possible.

minimumBribes has the following parameter(s):

Sample Input

2
5
2 1 5 3 4
5
2 5 1 3 4

Output

3
Too chaotic

Using the sorting logic I have just counted the person that comes early and are greater than following person. And it also prints the total no of bribes if the line configuration is possible else it prints Too chaotic message. 

static void minimumBribes(int[] q) {
    int count = 0; // Counts the no of bribes by an individual.
    int j;
    int total = 0; // Total no of bribes.

   loop1 : for(int i = 0; i < q.length; i++) {
      loop2 :  for(j = i; j < q.length; j++) {
            if(q[i] > q[j]) {
                count++;
                if(count > 2) {
                    System.out.println("Too chaotic");
                    break loop1;
                }

            }
            else if (q[i] <= q[j]) {
                total += count;
                count = 0;

            }
        }
    }
    if(count <= 2)    
    System.out.println(total);
}

The upper mentioned code runs perfectly for a small queue but if an array has a large size, It exceeds the fixed time limit for processing.

Upvotes: 0

Views: 133

Answers (2)

RBB
RBB

Reputation: 409

static void minimumBribes(int[] q) {
    int count = 0; // Counts the no of bribes by an individual.

    int total = 0; // Total no of bribes.

   loop1 : for(int i = 0; i < q.length; i++) {
              if((q[i]-(i+1))>2){//original position i should be person i+1 
                System.out.println("Too chaotic");
                break loop1;
              }  
              else if((q[i]-(i+1))>0){
                  count=q[i]-(i+1);
                  total += count;
                  count = 0;
              }
            }



    if(count <= 2)    //not sure what dose this sentence do?
    System.out.println(total);
}

Is this what you ask? Not sure I understand you correctlly

Upvotes: 0

smac89
smac89

Reputation: 43068

I just solved this in python to get a better understanding of the problem.

I decided to start with the last person in the queue because there are a number of things we can immediately say about this person:

  1. They can only bribe forward (i.e. they have no one behind them to bribe them)
  2. They cannot bribe to be more than two positions away from the "EOQ" [, where EOQ means end of queue or initial position of this person].

We can apply this rule to everyone starting from person N to person 1.

Pseudocode:

FOR PERSON in [N to 1]:
  P = PERSON
  IF (P MORE THAN 2 POSITIONS FROM INITIAL POS; OR P IS FURTHER BACK IN QUEUE):
    PRINT 'Too chaotic'
    RETURN

  FOR POS in [CURR_POS[P] to INIT_POS[P]]:     
     SWAP POSITION OF P AND PERSON_TO_THE_RIGHT_OF_P
     INCREMENT COUNT OF BRIBES BY 1

PRINT COUNT_OF_BRIBES

Notes

  • INIT_POS[P] refers to the initial position of the person before any bribes took place, so INIT_POS[PERSON_5] = 5

  • CURR_POS[P] refers to the current position of P at the start of the algorithm or after any swaps.

  • At the end of this algorithm, (assuming the bribes were not chaotic) the following invariant should hold: CURR_POS[i] == i. The reason is because all we are doing is moving all the people back to their original positions before any bribes took place.

Upvotes: 1

Related Questions