FastPrepCount Components With a Prime Total Value
Problems/Count Components With a Prime Total Value

Count Components With a Prime Total Value

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report published in September 2017 describes a Nutanix on-campus drive for interns. In the first face-to-face round, the author got a graph whose vertices each carry a value. They had to count the connected components whose vertex values add up to a prime.

The report gives no input format, value range, examples or limits. Here we chose the following. Vertices are numbered 0 to n - 1 with their values in an array. The undirected edges come as a list of pairs with no self-loops or repeated pairs. A vertex with no edges is a component by itself. Values are whole numbers from 0 to 10^5. The usual prime rule applies, so totals 0 and 1 do not count. There are at most 10^4 vertices and 2 * 10^4 edges, so a total is at most 10^9. The answer is the number of such components.

Our version is about 90% the same as the reported question.

You are given an undirected graph with n vertices labeled from 0 to n - 1, where n = values.length. Vertex i has the value values[i]. Each edges[j] = [a, b] joins vertices a and b, and you can move along an edge in either direction.

A connected component is a largest group of vertices in which every vertex can reach every other vertex by following edges. A vertex with no edges is a component by itself. The total of a component is the sum of the values of all its vertices.

Return the number of connected components whose total is a prime number. A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself, so the totals 0 and 1 are not prime.

Function

countPrimeComponents(values: int[], edges: int[][]) → int

Examples

Example 1

values = [3,4,1,6,7,2]edges = [[0,1],[1,2],[3,4]]return = 2

There are three components. Vertices 0, 1 and 2 have total 3 + 4 + 1 = 8, which is not prime. Vertices 3 and 4 have total 6 + 7 = 13, which is prime. Vertex 5 has no edges, so it is a component by itself with total 2, which is prime. Two components have a prime total.

Example 2

values = [1,0,1,0]edges = [[1,3]]return = 0

The components are {0} with total 1, {1, 3} with total 0, and {2} with total 1. Neither 0 nor 1 is prime, so the answer is 0.

Example 3

values = [4,9,6,1,10]edges = [[0,1],[2,3],[1,4]]return = 2

No single vertex value here is prime. The component {0, 1, 4} has total 4 + 9 + 10 = 23 and the component {2, 3} has total 6 + 1 = 7. Both totals are prime, so the answer is 2.

Constraints

  • 1 <= n == values.length <= 10^4
  • 0 <= values[i] <= 10^5
  • 0 <= edges.length <= 2 * 10^4
  • edges[j].length == 2
  • 0 <= edges[j][0], edges[j][1] <= n - 1
  • edges[j][0] != edges[j][1]
  • No two edges join the same pair of vertices.

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int countPrimeComponents(int[] values, int[][] edges) {
        // Write your code here.
    }
}
Checking account…