Google | OA Summer Intern 2020 | Greatest Common Divisor
Saba Khukhunashvili
28753
GoogleSingaporeOnline AssessmentInterview

Google Singapore OA Question
Summer 2020 Internship
Interview on CoCubes

Question #1:

GCD (Greatest Common Divisor) of two positive integers is the largest positive integer that divides both numbers without a remainder.
Siblings: Nodes with the same parent are called siblings.
Level of a tree: Level of a tree is the number of edges on the longest path from the root node to a leaf.
You are given nodes of a binary tree of leven n as input.
Caluclate the GCD of each pair of siblings and then find the max & min GCD among them. Print the difference of max & min GCD ( max GCD - min GCD)

Note:

  • Print -1 if input tree is empty i.e level of tree is -1.
  • Consider those nodes which have a sibling
  • Print 0 if no such pair of siblings found

Input Format:

The input is in the following format:

  • The first line takes an integer n as input which represents the level of tree (the root node is at 0 level). (if level is equal to -1, means empty tree)
  • Next n+1 lines contain the nodes in the tree level order. Each i'th line represents the nodes present in the binary tree in i'th level.

1st line contains level 0 nodes. (i.e. root node).
2nd line contains nodes for level 1.
3rd line contains nodes for level 2 and so on.
Each node is represented by an integer value. Node value of -1 denotes an empty node(no node present at that place).

Output Format:

A single integer i.e., the difference of max & min GCD (max GCD - min GCD)

Constraints:

  • -1 <= level of tree <= 20
  • 0 < element at nodes of tree <= 500
Comments (22)