Back
Close
  • 174

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

For a given multi-digit number N, determine on what single-digit positive number B it first deviates from the normal behavior of congruent clumping, if any.

What does that mean? Consider as an example:


N = 157285
B = 2


Split up the digits of N into a minimum number of clumps such that all of the digits D in each clump are modularly congruent in base B (meaning D % B is the same value):


clumps = [157, 28, 5]
D % B = [1, 0, 1]


Notice how for base 2, there are 3 clumps in this example. It can be observed that there would be more clumps if we used base 3 instead:


clumps = [1, 5, 7, 285]
D % B = [1, 2, 1, 2]


In fact, for the number 157285, the number of clumps for each base from 1-9 is nondecreasing.


N = 157285
base 1: [157285]
base 2: [157, 28, 5]
base 3: [1, 5, 7, 285]
base 4: [15, 7, 2, 8, 5]
base 5: [1, 5, 72, 8, 5]
base 6: [1, 5, 7, 28, 5]
base 7: [1, 5, 7, 2, 8, 5]
base 8: [1, 5, 7, 2, 8, 5]
base 9: [1, 5, 7, 2, 8, 5]


We will call this property the normal behavior of congruent clumping. However, not all numbers do this. For example, the number 25747 has 4 clumps in base 2 but only 2 clumps in base 3:


N = 25747
base 2: [2, 57, 4, 7]
base 3: [25, 747]


For this N, since base 3 contains less clumps than base 2, we would say the number deviates from the normal behavior of congruent clumping at base 3.

Some numbers only deviate on the higher values of B. For example, the number 338066 is normal up until base 8:


N = 338066
base 7: [33, 8, 0, 66]
base 8: [33, 80, 66]
Input
Line 1: N given as a string
Output
Either a digit B, from 1 to 9 inclusively, indicating the first deviation from the normal behavior of congruent clumping, or Normal if there is no deviation
Constraints
10 ≤ N ≤ 10^1000
Example
Input
157285
Output
Normal

A higher resolution is required to access the IDE