Back
Close

The Balanced Centrifuge Problem

Statement

 Goal

(Inspired by https://www.youtube.com/watch?v=7DHE8RnsCQ8)

Centrifuge is a piece of equipment that puts multiple test tubes in rotation at very high speeds. It consists of a cylindrical rotor with holes situated evenly along the circumference of the rotor.
Because the device is operating at high speeds, the center of mass of all tubes must coincide with the center of the rotor. We assume all tubes have the same mass.

For the sake of simplicity, we also assume that tubes are point masses, fixed firmly to the rotor. All at the same distance from the center. You may safely assume the (x,y) coordinates of tube k are (R*sin (a), R*cos (a)), where a = 2*Pi*k/n;

The problem is: Given a centrifuge with N holes and K tubes, is it possible to balance it?

example 1: given N = 6 possible values for K are 2,3,4,6.

example 2: given N = 12, it is possible to balance 5 tubes: put 3 evenly dispersed (every 4th hole), then find a pair of opposite unoccupied holes and insert remaining 2 tubes there.

example 3: given N = 10, it is impossible to balance 7 tubes: put 5 evenly dispersed, and there's no opposite unoccupied holes left!
Input
Line 1: An integer N for the capacity of the centrifuge.
Output
Line 1: An integer M for the number of different possible values of K.
Constraints
2<=N<=200000
1 <= K <= N
1 <= M <= N
Example
Input
7
Output
1

Tags
PrimesDynamic programming

Difficulty
Hard

Test cases
Prime Test
Input
7
Output
1

Validator 1 Validator
Input
13
Output
1

Small Composite Test
Input
6
Output
4

Validator 2 Validator
Input
8
Output
4

Medium Composite Test
Input
12
Output
10

Validator 3 Validator
Input
18
Output
16

Two Primes Test
Input
33
Output
13

Validator 4 Validator
Input
35
Output
11

Hard 1 Test
Input
2695
Output
2679

Validator 5 Validator
Input
1911
Output
1899

Hard 2 Test
Input
12345
Output
12337

Validator 6 Validator
Input
23457
Output
23445

Tricky Test
Input
136271
Output
135543

Validator 7 Validator
Input
169979
Output
169011

Power of a Prime Test
Input
131072
Output
65536

Validator 8 Validator
Input
177147
Output
59049

Solution language

Solution

Stub generator input
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants