Given an array of integers arr, sort the array by performing a series of pancake flips.   In one pancake flip we do the following steps: Choose an integer k where 1 <= k <= arr.length. Reverse the sub-array arr[0...k-1] (0-indexed). For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.   Print out the k-values corresponding to a sequence of pancake flips that sort arr.   Example 1: Input: arr = [3,2,4,1] Output: 4, 2, 4, 3 Explanation: We perform 4 pancake flips, with k values 4, 2, 4, and 3. Starting state: arr = [3, 2, 4, 1]. After 1st flip (k = 4): arr = [1, 4, 2, 3] After 2nd flip (k = 2): arr = [4, 1, 2, 3] After 3rd flip (k = 4): arr = [3, 2, 1, 4] After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.   Another potential solution is: Output = 3, 4, 2, 3, 1, 2, 1, 1 with a similar explanation. All potential solutions that solve the problem are accepted.   Example 2: Input: arr = [1,2,3] Output: [] Explanation: The input is already sorted, so there is no need to flip anything. Note that other answers, such as [3, 3], would also be accepted.   Constraints: 1 <= arr.length <= 100 1 <= arr[i] <= arr.length All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length). ======================================================================================= class Solution {     public static void pancakeSort(int[] inputArray) {              }          private static int find(int[] A, int target) {            }     private static void flip(int[] A, int index) {              }     public static void main(String[] args){         int[] arr = {3,2,4,1};         pancakeSort(arr);     } }

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Given an array of integers arr, sort the array by performing a series of pancake flips.

 

In one pancake flip we do the following steps:

  • Choose an integer k where 1 <= k <= arr.length.

  • Reverse the sub-array arr[0...k-1] (0-indexed).

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

 

Print out the k-values corresponding to a sequence of pancake flips that sort arr.

 

Example 1:

Input: arr = [3,2,4,1]

Output: 4, 2, 4, 3

Explanation: We perform 4 pancake flips, with k values 4, 2, 4, and 3.

Starting state: arr = [3, 2, 4, 1].

After 1st flip (k = 4): arr = [1, 4, 2, 3]

After 2nd flip (k = 2): arr = [4, 1, 2, 3]

After 3rd flip (k = 4): arr = [3, 2, 1, 4]

After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

 

Another potential solution is: Output = 3, 4, 2, 3, 1, 2, 1, 1 with a similar explanation. All potential solutions that solve the problem are accepted.

 

Example 2:

Input: arr = [1,2,3]

Output: []

Explanation: The input is already sorted, so there is no need to flip anything. Note that other answers, such as [3, 3], would also be accepted.

 

Constraints:

  • 1 <= arr.length <= 100

  • 1 <= arr[i] <= arr.length

  • All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

=======================================================================================

class Solution {
    public static void pancakeSort(int[] inputArray) {
        
    }
    
    private static int find(int[] A, int target) {
      
    }
    private static void flip(int[] A, int index) {
        
    }

    public static void main(String[] args){
        int[] arr = {3,2,4,1};
        pancakeSort(arr);
    }
}
Expert Solution
steps

Step by step

Solved in 4 steps with 2 images

Blurred answer
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question

can you do it without the 

        List<Integer> flips = new ArrayList<>();
?
Solution
Bartleby Expert
SEE SOLUTION
Knowledge Booster
Arrays
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education