Searching Huge Sets (von Neumann Hierarchy)

Given any set, say S = {1, 2, 3}, it's power set is defined as the set of all subsets of S. So power set of S is {{}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}.

Now define a sequence V such that V_0 = {} and V_{i + 1} = power set of V_i. So

V_0 = {}

V_1 = { {} }

V_2 = { {}, {{}} }

V_3 = { {}, {{}}, {{{}}}, {{}, {{}}} }

and so on.

Now given any arbritrary set A, write a program to compute the smallest k such that A is a member of V_k.

Examples

When A = {{{}}}, k = 3.

When A = {{}, {{}, {{}}}}, k = 4.

The input will be provided with no commas or spaces. So {{}, {{}, {{}}}} = {{}{{}{{}}}}

Time Limit: 1s

Max length of input = 10^6

Sample Test Case with 113280 characters

Solution to the sample test case

263

Read more…(164 words)

About the author:

YG

Yasharyan Gaikwad

Loading…

Join the discussion. Add a reply…

Post

About the author

YG

Yasharyan Gaikwad

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.