1.Codewriting
A positive integer is "fancy" if its representation in base 4 only includes 0s and 1s. For example:
- 17 is fancy: its base-4 representation, 101, only includes 0s and 1s.
- 18 is not fancy: its base-4 representation, 102, includes a 2.
Given a positive integer nn, find the number of fancy positive integers less than nn.
Note that nn may be as large as a billion! Your algorithm should be faster than iterating over values less than nn and checking if each one is fancy.
Example
- For n=1n = 1, the output should be 0; there are no positive integers less than 1.
- For n=10n = 10, the output should be 3, since {1, 4, 5} are all fancy.
Input/Output
[Execution time limit]
4 seconds (py3)
[Memory limit]
1 GB
[Input] integer nn
An upper bound on the range.
Guaranteed constraint:
0<n≤1090 < n × 10^9
[Output]
integer
[Python 3] Syntax Tips
# Prints help message to the console
# Returns a string
def helloWorld(name):
print("This prints to the console when you Run Tests")
return "Hello, " + name
2.Class Definition
class Node:
key: int (0 <= key <= 10,000)
value: int (0 <= value <= 1,000,000,000)
children: list[Node (or Node pointers in C++)]
Each node of the tree has a key, value, and references to each of its children. Children are ordered—the order of the children list matters. A node with no children will have an empty list for its children attribute.
Throughout this explanation, we will use the shorthand a@ba@b to refer to a node with key aa and value bb—this doesn't necessarily uniquely identify a node since two nodes can share a key if they are not children of the same parent, and any two nodes can share the same value.
We will pass in trees as a list of lists of integers. Each row of the input is itself a list of integers that represents a node.
Input Format
The format of each row of the input is as follows:
- The first element represents that node's key.
- The second element represents that node's value.
- All subsequent elements represent, in order, the row index of that node's children (using a 0-indexing convention).
The rows may be passed in an arbitrary order, but you can assume that they form a well-formed tree with a unique root. For any given node, all its children must have unique keys (the input is guaranteed to satisfy this).
This is the only uniqueness guarantee:
- Two nodes that are not children of the same parent can have the same key.
- Any two nodes can have the same value.
Example
Input:
[
[4, 2],
[1, 15, 3, 2, 0],
[1, 0, 4],
[6, 3, 2, 3]
]
Explanation
- The interpretation of the 0-index row
[4, 2]is a node with key 4 and value 2. - The interpretation of the 1-index row
[1, 15, 3, 2, 0]is a node with key 1, value 15, and children corresponding to:- The 3-index row (6@36@3),
- The 2-index row (1@01@0),
- The 0-index row (4@24@2).
Resultant Tree Structure
1@15
/ | \
6@3 1@0 4@2
|
2@3
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
