672. Bulb Switcher II

leetcode medium

#csharp#hash-table#leetcode#math#medium#string

Task

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:

Кнопка 1: Переключает состояние всех лампочек.

Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).

Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).

Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).

Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.

Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1

Output: 2

Explanation: Status can be:

- [off] by pressing button 1

- [on] by pressing button 2

C# solution

matched/original

public class Solution {
    public int FlipLights(int n, int m) {
        var seen = new HashSet<int>();
        n = Math.Min(n, 6);
        int shift = Math.Max(0, 6 - n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Convert.ToString(cand, 2).Count(c => c == '1');
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.Add(lights);
            }
        }
        return seen.Count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FlipLights(int n, int m) {
        var seen = new HashSet<int>();
        n = min(n, 6);
        int shift = max(0, 6 - n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Convert.ToString(cand, 2).size()(c => c == '1');
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.push_back(lights);
            }
        }
        return seen.size();
    }
}

Java solution

matched/original

class Solution {
    public int flipLights(int n, int m) {
        Set<Integer> seen = new HashSet<>();
        n = Math.min(n, 6);
        int shift = Math.max(0, 6 - n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Integer.bitCount(cand);
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.add(lights);
            }
        }
        return seen.size();
    }
}

JavaScript solution

matched/original

var flipLights = function(n, m) {
    let seen = new Set();
    n = Math.min(n, 6);
    let shift = Math.max(0, 6 - n);
    for (let cand = 0; cand < 16; ++cand) {
        let bcount = cand.toString(2).split('1').length - 1;
        if (bcount % 2 == m % 2 && bcount <= m) {
            let lights = 0;
            if ((cand >> 0) & 1) lights ^= 0b111111 >> shift;
            if ((cand >> 1) & 1) lights ^= 0b010101 >> shift;
            if ((cand >> 2) & 1) lights ^= 0b101010 >> shift;
            if ((cand >> 3) & 1) lights ^= 0b100100 >> shift;
            seen.add(lights);
        }
    }
    return seen.size;
}

Python solution

matched/original

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        seen = set()
        n = min(n, 6)
        shift = max(0, 6 - n)
        for cand in range(16):
            bcount = bin(cand).count('1')
            if bcount % 2 == m % 2 and bcount <= m:
                lights = 0
                if ((cand >> 0) & 1) > 0: lights ^= 0b111111 >> shift
                if ((cand >> 1) & 1) > 0: lights ^= 0b010101 >> shift
                if ((cand >> 2) & 1) > 0: lights ^= 0b101010 >> shift
                if ((cand >> 3) & 1) > 0: lights ^= 0b100100 >> shift
                seen.add(lights)
        return len(seen)

Go solution

matched/original

import (
    "math/bits"
)

func flipLights(n int, m int) int {
    seen := make(map[int]struct{})
    n = min(n, 6)
    shift := max(0, 6-n)

    for cand := 0; cand < 16; cand++ {
        bcount := bits.OnesCount(uint(cand))
        if bcount % 2 == m % 2 && bcount <= m {
            lights := 0
            if (cand>>0)&1 > 0 { lights ^= 0b111111 >> shift }
            if (cand>>1)&1 > 0 { lights ^= 0b010101 >> shift }
            if (cand>>2)&1 > 0 { lights ^= 0b101010 >> shift }
            if (cand>>3)&1 > 0 { lights ^= 0b100100 >> shift }
            seen[lights] = struct{}{}
        }
    }

    return len(seen)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎