Distribute in Circle | InterviewBit | Solution Explained

I explain the solution to Distribute in Circle InterviewBit problem. Using visuals and intuitions for the mathematical solution. Problem Link.

0. Distribute in Circle: Problem Discussion

0.0. IO Format

• input:
  • A: number of items
  • B: size of circle
  • C: starting point inside the circle
• output:
  • position where the Ath item (last) will get delivered
• constraints:
  • 1 <= A, B, C <= 10⁸

0.1. Examples

In this case, we have

• a circle of B size – marked in blue.
• inside of the circle, we first move to the Cth position (zero indexed)
• then start distributing A items from that position

In this case, we start from index C = 4, then go in the clockwise direction in the circle B = 5 and distribute A = 7 items. The last item is distributed at the 0th index, which is thus the answer.

1. Distribute in Circle: Observations & Logic

1.0. Intuitions

One solid point to notice is that we are stuck inside a circle, so the Ath item only has an effect of A % B. What it means is, if we have A = 7 and B = 5, we basically will allocate A / B = 1 items to everyone, then the next A % B = 2 people will get one more item than the rest. NOTE: the minus 1 is done because we will be at A % B position when we have successfully distributed everything. That means that the last index that we actually distributed was actually A % B – 1.

formula = A % B – 1

Now where does C come into play? Think of it as an initial displacement – we could have started from 0th index, and returned the answer as A % B – 1. C just comes in, and displaces everything by C amount.

formula = (C + A % B – 1) % B

NOTE: we have again done % B since the value inside the brackets can actually go beyond B. Think why!

2. Distribute in Circle: Optimized Implementation

2.0. Code

int Solution::solve(int A, int B, int C) {
    return (C + A % B - 1) % B;
}

2.1. Complexity Analysis

• Time: O(1), since we only do O(1) operations
• Space: O(1), since we never use any variable ourselves.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.