CODEWITHSUNDEEP
algorithm
Saurabh
Saurabh

Reputation: 156

Brute Force permutations

I was reading the following article and couldn't understand the logic behind the 4th paragraph

You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd lamps, and last switch toggles lamps 1, 4, 7, 10, ... .

Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps (e.g., lamp 7 is off), output all the possible states the lamps could be in.

Naively, for each button press, you have to try 4 possibilities, for a total of 4^10000 (about 10^6020 ), which means there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about 10000^4 (about 10^16 ), still too big to completely search (but certainly closer by a factor of over 10^6000 ).

However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing each button either 0 or 1 times. That's only 2^4 = 16 possibilities, surely a number of iterations solvable within the time limit.

When order doesn't matter how the number of total configurations is 10000^4 ?

Upvotes: 1

Views: 354

Answers (1)

Gareth McCaughan
Gareth McCaughan

Reputation: 19981

The author is stipulating that the number of button presses is limited to 10,000:

the number of button presses made (up to 10,000)

and if you know the order of button presses doesn't matter, but nothing else, then all that matters is how many times each button has been pressed. There are 10,000 possibilities for each of 4 buttons, so about 10000^4 overall. (Of course the real number is a bit smaller because you can't, e.g., have pressed all four buttons 10,000 times each.)

Upvotes: 2

Related Questions