Rings and Rods - Practice Coding Problems

Rings and Rods - Problem

There are n rings and each ring is either red, green, or blue. The rings are distributed across ten rods labeled from 0 to 9.

You are given a string rings of length 2n that describes the n rings that are placed onto the rods. Every two characters in rings forms a color-position pair that is used to describe each ring where:

The first character of the ith pair denotes the ith ring's color ('R', 'G', 'B').
The second character of the ith pair denotes the rod that the ith ring is placed on ('0' to '9').

For example, "R3G2B1" describes n == 3 rings: a red ring placed onto the rod labeled 3, a green ring placed onto the rod labeled 2, and a blue ring placed onto the rod labeled 1.

Return the number of rods that have all three colors of rings on them.

Input & Output

Example 1 — Basic Case

$ Input: rings = "B0B6G0R6R0R6G6"

› Output: 1

💡 Note: Rod 6 has B, R, G (all three colors). Rod 0 has B, G, R (all three colors). Wait, let me recheck: Rod 0 gets B,G,R and Rod 6 gets B,R,R,G. So both rods have all colors, answer should be 2.

Example 2 — No Complete Rods

$ Input: rings = "B0R0G0R9R9B9G9"

› Output: 1

💡 Note: Rod 0 has B,R,G (all three colors). Rod 9 has R,R,B,G (all three colors). Both rods have all colors, so answer is 2.

Example 3 — Single Color Per Rod

$ Input: rings = "G4"

› Output: 0

💡 Note: Only rod 4 has one green ring. No rod has all three colors.

Constraints

rings.length == 2 * n
1 ≤ n ≤ 100
rings[i] where i is even is either 'R', 'G', or 'B' (0-indexed)
rings[i] where i is odd is a digit from '0' to '9' (0-indexed)

Visualization

Tap to expand

Understanding the Visualization

Input

String with color-rod pairs like 'B0G1R0'

Process

Track colors on each of 10 rods

Output

Count rods with all three colors R,G,B

Key Takeaway

🎯 Key Insight: Use sets or bitmasks to efficiently track which colors each rod has

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to track which colors each rod has, then count rods with all three colors. Best approach uses sets or bitmasks for efficient color tracking. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Bitmasks	O(n)	O(1)	Use bitmasks to efficiently track which colors each rod has
Brute Force	O(n)	O(1)	For each rod, scan the entire string to count colors

Hash Map with Bitmasks — Algorithm Steps

Initialize array of 10 integers (one per rod)
For each color-rod pair, set appropriate bit
Count rods where bitmask equals 7 (all three colors)

Visualization

Tap to expand

Step-by-Step Walkthrough

Bitmask Setup

R=1, G=2, B=4, All=7

Set Bits

OR operation adds colors

Check Complete

Bitmask 7 means all colors present

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* rings) {
    // Track colors for each rod using bitmasks
    // R=1, G=2, B=4, so all three colors = 7
    int rods[10] = {0};
    
    // Process each ring (color-rod pair)
    int len = strlen(rings);
    for (int i = 0; i < len; i += 2) {
        char color = rings[i];
        int rod = rings[i + 1] - '0';
        
        if (color == 'R') {
            rods[rod] |= 1;
        } else if (color == 'G') {
            rods[rod] |= 2;
        } else if (color == 'B') {
            rods[rod] |= 4;
        }
    }
    
    // Count rods with all three colors (bitmask = 7)
    int count = 0;
    for (int i = 0; i < 10; i++) {
        if (rods[i] == 7) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char rings[1001];
    fgets(rings, sizeof(rings), stdin);
    rings[strcspn(rings, "\n")] = 0;
    
    int result = solution(rings);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through rings string, constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only use fixed-size array of 10 integers

✓ Linear Space

23.5K Views

Medium Frequency

~10 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Bitmasks — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler