FastPrep
Problem · Array

Alternating Parity Permutations

Learn this problem
● MediumGoldman SachsINTERNOA

Problem statement

An e-commerce company is writing a fuzzer to test a piece of its software. They need a list of numbers with alternating parity, that is, one of them is odd and the other one is even.

An alternating parity permutation is a permutation in which any two adjacent elements have different parity. For example, [1,2,3,4], [1], and [3,2,1] exhibit alternating parity, while [1,3,2] and [4,2,1,3] do not.

For a given integer n, return all alternating parity permutations of the first n positive integers in lexicographically ascending order. Each permutation contains n elements. For example, the first four permutations where n = 10 are:

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 10 9 8
1 2 3 4 5 6 9 8 7 10
1 2 3 4 5 6 9 10 7 8

Function

alternatingParityPermutations(n: int) → int[][]

Examples

Example 1

n = 4return = [
  [1, 2, 3, 4],
  [1, 4, 3, 2],
  [2, 1, 4, 3],
  [2, 3, 4, 1],
  [3, 2, 1, 4],
  [3, 4, 1, 2],
  [4, 1, 2, 3],
  [4, 3, 2, 1]
]

The values of the array are from 1 to n. The following are alternating parity permutations of the first 4 positive integers, sorted. Any other permutation will result in adjacent elements sharing the same parity.

More Goldman Sachs problems

drafts saved locally
public int[][] alternatingParityPermutations(int n) {
  // write your code here
}
n4
expected[ [1, 2, 3, 4], [1, 4, 3, 2], [2, 1, 4, 3], [2, 3, 4, 1], [3, 2, 1, 4], [3, 4, 1, 2], [4, 1, 2, 3], [4, 3, 2, 1] ]
checking account