bits/
lib.rs

1//! # Bits (aka Bitwise)
2
3/// 36m Valid Sudoku
4struct Sol36 {}
5
6impl Sol36 {
7    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
8        let (mut rows, mut cols, mut cells) = ([0; 9], [0; 9], [0; 9]);
9        for (r, row) in board.iter().enumerate() {
10            for (c, mask) in row
11                .iter()
12                .enumerate()
13                .filter(|&(_, &chr)| chr != '.')
14                .map(|(c, chr)| (c, 1 << chr.to_digit(10).unwrap() - 1))
15            {
16                if rows[r] & mask == mask {
17                    return false;
18                }
19                rows[r] |= mask;
20
21                if cols[c] & mask == mask {
22                    return false;
23                }
24                cols[c] |= mask;
25
26                if cells[3 * (r / 3) + c / 3] & mask == mask {
27                    return false;
28                }
29                cells[3 * (r / 3) + c / 3] |= mask;
30
31                println!(
32                    "-> {r},{c}:{} :: {rows:>3?} {cols:>3?} {cells:>3?}",
33                    3 * (r / 3) + c / 3
34                );
35            }
36        }
37
38        true
39    }
40}
41
42/// 868 Binary Gap
43struct Sol868;
44
45impl Sol868 {
46    pub fn binary_gap(n: i32) -> i32 {
47        let (mut dist, mut cur) = (0, -32);
48
49        let mut n = n;
50        while n > 0 {
51            cur += 1;
52            dist = dist.max(cur);
53            if n & 1 == 1 {
54                cur = 0;
55            }
56            n >>= 1;
57        }
58
59        dist
60    }
61}
62
63/// 1863 Sum of All Subset XOR Totals
64struct Sol1863;
65
66impl Sol1863 {
67    pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
68        fn search(nums: &[i32], start: usize, xor: i32) -> i32 {
69            if start == nums.len() {
70                return xor;
71            }
72
73            search(nums, start + 1, xor) + search(nums, start + 1, nums[start] ^ xor)
74        }
75
76        search(&nums, 0, 0)
77    }
78
79    fn subset_xor_sum_bitwise(nums: Vec<i32>) -> i32 {
80        let mut xsum = 0;
81        for n in &nums {
82            xsum |= n;
83        }
84
85        xsum << (nums.len() - 1)
86    }
87}
88
89/// 2438m Range Product Queries of Powers
90struct Sol2438 {}
91
92impl Sol2438 {
93    pub fn product_queries(mut n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
94        let mut powers = vec![];
95
96        let mut power = 1;
97        while n > 0 {
98            if n & 1 == 1 {
99                powers.push(power);
100            }
101            power <<= 1;
102            n >>= 1;
103        }
104
105        powers.sort();
106        println!("-> {powers:?}");
107
108        const M: i64 = 1e9 as i64 + 7;
109        queries
110            .iter()
111            .map(|query| (query[0] as usize, query[1] as usize))
112            .map(|(l, r)| {
113                powers
114                    .iter()
115                    .take(r + 1)
116                    .skip(l)
117                    .fold(1, |prd, &n| prd * n % M)
118            })
119            .map(|prd| prd as i32)
120            .collect()
121    }
122}
123
124#[cfg(test)]
125mod tests;
bits/lib.rs

bits/
lib.rs
