3011. Find if Array Can Be Sorted Medium

1/**
2 * [3011] Find if Array Can Be Sorted
3 *
4 * You are given a 0-indexed array of positive integers nums.
5 * In one operation, you can swap any two adjacent elements if they have the same number of <span data-keyword="set-bit">set bits</span>. You are allowed to do this operation any number of times (including zero).
6 * Return true if you can sort the array in ascending order, else return false.
7 *  
8 * <strong class="example">Example 1:
9 * 
10 * Input: nums = [8,4,2,30,15]
11 * Output: true
12 * Explanation: Let's look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation "10", "100", and "1000" respectively. The numbers 15 and 30 have four set bits each with binary representation "1111" and "11110".
13 * We can sort the array using 4 operations:
14 * - Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
15 * - Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
16 * - Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
17 * - Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30].
18 * The array has become sorted, hence we return true.
19 * Note that there may be other sequences of operations which also sort the array.
20 * 
21 * <strong class="example">Example 2:
22 * 
23 * Input: nums = [1,2,3,4,5]
24 * Output: true
25 * Explanation: The array is already sorted, hence we return true.
26 * 
27 * <strong class="example">Example 3:
28 * 
29 * Input: nums = [3,16,8,4,2]
30 * Output: false
31 * Explanation: It can be shown that it is not possible to sort the input array using any number of operations.
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= nums.length <= 100
37 * 	1 <= nums[i] <= 2^8
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/find-if-array-can-be-sorted/
43// discuss: https://leetcode.com/problems/find-if-array-can-be-sorted/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn can_sort_array(nums: Vec<i32>) -> bool {
49        false
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_3011() {
61    }
62}
63