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 <= 108

0.1. Examples

Distribute in Circle: Example explanation
Distribute in Circle: Example explanation

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.
Avatar for Tanishq Chaudhary

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

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.