New Year Chaos

Sort by

recency

|

71 Discussions

|

  • + 0 comments

    pyhton 3

    def minimumBribes(q):
        # Write your code here
        total_steps = 0
        n = len(q)
        for i in range(n):
            # Check if the element has moved more than two positions forward
            if q[i] - (i + 1) > 2:
                return print("Too chaotic")
                
            for j in range(max(0, q[i] - 2), i):
                    if q[j] > q[i]:
                        total_steps += 1
        
        return print(total_steps )
    
  • + 0 comments

    Javascript

    It's essentially a reverse insertion sort. You just keep looping through the array doing a single swap until it's sorted. Count how many times you had to make a swap to get it sorted. Break if the value of any element is more than two higher than its original position.

    function minimumBribes(q: number[]): void {
      let totalBribes = 0;
      
      let sorted = false;
      
      while (sorted === false) {
        sorted = true;
        
        for (let i=0; i < q.length-1; i++) {
          if (q[i] > q[i+1]) {
            if (q[i] - (i+1) > 2) {
              console.log('Too chaotic');
              return;
            }
            const temp = q[i];
            q[i] = q[i+1];
            q[i+1] = temp;
            sorted = false;
            totalBribes++;
          }
        }
      }
      
      console.log(totalBribes);
    }
    
  • + 0 comments

    Here is HackerRank New year chaos problem solution in Python, java, C++, C and javascript

  • + 0 comments

    Can't shake the feeling that other solutions and explanations are just too complicated.

    Observations: - This is a que of people, normally always starts 1,2,3,4... - Since person can skip at most 2 positions, it means that if we look at que segment of size 3, we known that for arbirary position i only i, i+1 and i+2 can be there - So for initial segment [p1,p2,p3] at position p1 can only be 1 (the original), 2 (if it bribed) or 3 (if it bribed twice)

    So if normally the queue was supposed to start with [p1, p2, p3] = [1, 2, 3] , then by scanning the queue from left to right (via var x) and keeping track of p1, p2, p3 we can encounter the following cases

    1) x == p1 // x is at it's place and did not bribe anyone
    p1, p2, p3 = p2, p3, p3+1 // shift the window to the right

    2) x == p2 // x bribed once and skipepd 1 ahead bribes += 1 p2, p3 = p3, p3+1 // expected p1 is the same, p2 and p3 move to the right

    3) x == p3 // x bribed twice and skipped 2 ahead bribes += 2 p3 = p3+1 // we are still expecting the same p1 and p2, p3 moves to the right

    4) x is outside the window thus it's chaos

    Code in golang

    func minimumBribes(q []int32) {
    	// Write your code here
    	var bribes int32
    	// window of size 3
    	// starts by expecting the right order
    	var p1, p2, p3 int32 = 1, 2, 3
    
    	for _, x := range q {
    		switch {
    		// x = 1;  1 2 3 -> 2 3 4
    		case x == p1:
    			p1, p2, p3 = p2, p3, p3+1
    		// x = 2; 2 1 3 -> 1 3 4
    		case x == p2:
    			bribes += 1
    			p2, p3 = p3, p3+1
    		// x = 3; 3 1 2 -> 1 2 4
    		case x == p3:
    			bribes += 2
    			p3 = p3 + 1
    		default:
    			fmt.Println("Too chaotic")
    			return
    		}
    	}
    
    	fmt.Println(bribes)
    }
    
  • + 0 comments

    Java

    public static void minimumBribes(List<Integer> q) {
            int bribe = 0;
            for (int i = q.size()-1; i > 0; i--){
                if (q.get(i) != i+1){
                    if (q.get(i-1) == i+1){
                        int temp = q.get(i-1);
                        q.set(i-1, q.get(i));
                        q.set(i, temp);
                        bribe++;
                    }
                    else if (q.get(i-2) == i+1){
                        int temp = q.get(i-2);
                        q.set(i-2, q.get(i-1));
                        q.set(i-1, q.get(i));
                        q.set(i, temp);
                        bribe += 2;
                    }
                    else{
                        System.out.println("Too chaotic");
                        return;
                    }
                }
            }
            System.out.println(bribe);
        }