花花酱 LeetCode 1175. Prime Arrangements

By zxi on August 31, 2019

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

Constraints:

1 <= n <= 100

Solution: Permutation

Count the number of primes in range [1, n], assuming there are p primes and n – p non-primes, we can permute each group separately.
ans = p! * (n – p)!

Time complexity: O(nsqrt(n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numPrimeArrangements(int n) {

const int kMod = 1e9 + 7;

int p = 0;

for (int i = 1; i <= n; ++i)

p += isPrime(i);

long ans = 1;

for (int i = 1; i <= p; ++i)

ans = (ans * i) % kMod;

for (int i = 1; i <= n - p; ++i)

ans = (ans * i) % kMod;

return ans;

}

private:

bool isPrime(int x) {

if (x < 2) return false;

if (x == 2) return true;

for (int i = 2; i <= sqrt(x); ++i)

if (x % i == 0) return false;

return true;

}

};

花花酱 LeetCode 31. Next Permutation

By zxi on October 2, 2018

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution

Find the last acceding element x, swap with the smallest number y, y is after x that and y is greater than x.

Reverse the elements after x.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 8 ms

class Solution {

public:

void nextPermutation(vector<int>& nums) {

int i = nums.size() - 2;

while (i >= 0 && nums[i + 1] <= nums[i]) --i;

if (i >= 0) {

int j = nums.size() - 1;

while (j >= 0 && nums[j] <= nums[i]) --j;

swap(nums[i], nums[j]);

}

reverse(begin(nums) + i + 1, end(nums));

}

};

Python3

# Author: Huahua, 48 ms

class Solution:

def nextPermutation(self, nums):

n = len(nums)

i = n - 2

while i >= 0 and nums[i] >= nums[i + 1]: i -= 1

if i >= 0:

j = n - 1

while j >= 0 and nums[j] <= nums[i]: j -= 1

nums[i], nums[j] = nums[j], nums[i]

nums[i + 1:] = nums[i+1:][::-1]

花花酱 LeetCode 47. Permutations II

By zxi on July 26, 2018

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution

Time complexity: O(n!)

Space complexity: O(n + k)

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

vector<vector<int>> permuteUnique(vector<int>& nums) {

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> used(nums.size());

vector<int> cur;

dfs(nums, cur, used, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, vector<int>& cur, vector<int>& used, vector<vector<int>>& ans) {

if (cur.size() == nums.size()) {

ans.push_back(cur);

return;

}

for (int i = 0; i < nums.size(); ++i) {

if (used[i]) continue;

// Same number can be only used once at each depth.

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

used[i] = 1;

cur.push_back(nums[i]);

dfs(nums, cur, used, ans);

cur.pop_back();

used[i] = 0;

}

};

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10ⁿ.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution: Math

f(0) = 1 (0)

f(1) = 10 (0 – 9)

f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))

f(3) = 9 * 9 * 8

f(4) = 9 * 9 * 8 * 7

…

f(x) = 0 if x >= 10

ans = sum(f[1] ~ f[n])

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if (n == 0) return 1;

vector<int> f(11);

f[1] = 10;

f[2] = 9 * 9;

for (int i = 3; i <= 10; ++i)

f[i] = f[i - 1] * (10 - i + 1);

int ans = 0;

for (int i = 0; i <= min(10, n); ++i)

ans += f[i];

return ans;

}

};

花花酱 LeetCode 384. Shuffle an Array

By zxi on March 16, 2018

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

C++

// Author: Huahua

// Running time: 249 ms

class Solution {

public:

Solution(vector<int> nums) {

nums_ = std::move(nums);

}

/** Resets the array to its original configuration and return it. */

vector<int> reset() {

return nums_;

}

/** Returns a random shuffling of the array. */

vector<int> shuffle() {

vector<int> output(nums_);

const int n = nums_.size();

for (int i = 0; i < n - 1; ++i) {

int j = rand() % (n - i) + i;

std::swap(output[i], output[j]);

}

return output;

}

private:

vector<int> nums_;

};

Posts tagged as “permutation”

花花酱 LeetCode 1175. Prime Arrangements

Solution: Permutation

C++

花花酱 LeetCode 31. Next Permutation

Problem

Solution

C++

Python3

花花酱 LeetCode 47. Permutations II

Problem

Solution

Related Problems

花花酱 LeetCode 357. Count Numbers with Unique Digits

Problem

Solution: Math

花花酱 LeetCode 384. Shuffle an Array