• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Possible sizes of bus to carry n groups of friends

December 14, 2014 by Dhaval Dave

There are n groups of friends, and each group is numbered from 1 to n. The ith group contains ai people. 
They live near a bus stop, and only a single bus operates on this route. An empty bus arrives at the bus stop and all the groups want to travel by the bus.

However, group of friends do not want to get separated. So they enter the bus only if the bus can carry the entire group.

Moreover, the groups do not want to change their relative positioning while travelling. In other words, group 3 cannot travel by bus, unless group 1 and group 2 have either (a) already traveled by the bus in the previous trip or (b) they are also sitting inside the bus at present.

 You are given that a bus of size x can carry x people simultaneously.

 Find the size x of the bus so that (1) the bus can transport all the groups and (2) every time when the bus starts from the bus station, there is no empty space in the bus (i.e. the total number of people present inside the bus is equal to x)?

 Input Format

The first line contains an integer n (1≤n≤105). The second line contains n space-separated integers a1,a2,…,an (1≤ai≤104).

 Output Format

 Print all possible sizes of the bus in an increasing order.

Sample Input

 8

1 2 1 1 1 2 1 3

Sample Output

 3 4 6 12

Sample Explanation

In the above example, a1 = 1, a2 = 2, a3 = 1, a4 = 1, a5 = 1, a6 = 2, a7 = 1, a8 = 3.

 If x = 1 : In the first trip, a1 go by the bus. There will be no second trip because the bus cannot accommodate group 2. Hence “x = 1” is not the required answer.

 If x = 2 : No bus trip is possible. That’s because a1 cannot go alone, as one seat will be left vacant in the bus. And, a1 & a2 cannot go together, because the bus is cannot accommodate both the groups simultaneously.

 If x = 3 : In the first trip, a1 & a2 go by the bus. In the second trip, a3, a4 & a5 go by the bus. In the third trip, a6 & a7 go by the bus. In the fourth trip, a8 go by the bus.

 If x = 4 : In the first trip, a1, a2 & a3 go by the bus. In the second trip, a4, a5 & a6go by the bus. In the third trip, a7 & a8 go by the bus.

Similarly you can figure out the output for x= 5, 6 & 7.

 
 Solution:

def find_possible_bus_sizes(numbers) sum_array = [] numbers.each { |num| sum_array << sum_array.last.to_i + num} max, total, out = numbers.max, sum_array.last, [] sum_array.each { |sum| out << sum if (sum>=max && total%sum==0) } out end find_possible_bus_sizes([3,4,6,7,2,1,3,4]) output :- [30] find_possible_bus_sizes([]) output :- [] find_possible_bus_sizes([1]) output :- [1] find_possible_bus_sizes([1,1,1,1]) output :- [1,2,4] find_possible_bus_sizes([1,2,1,1,1,2,1,3]) output :- [3,4,6,12] find_possible_bus_sizes([1,2,6,2,1,3]) output :- [15] find_possible_bus_sizes([1,2,1,1,1,2,1,4]) output :- [13] find_possible_bus_sizes([1,2,1,5,3]) output :- [12]

-Article by Praveen Sah

Similar Articles

Filed Under: Interview Questions, problem Tagged With: Mathematical

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Generate largest number arranging a no. of given non negative integer numbers

Client Server C program

LeetCode : Word Search

Closed Parentheses checker

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Daughter’s Age VeryGood Puzzle

Serialise Deserialise N-ary Tree

Leetcode: Merge Intervals

HackeEarth Flipkart’s Drone

Level order traversal in Spiral form

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

CodeChef’ RRCOPY

25 horses 5 tracks Find 3 fastest puzzle

Test Cases for Round Function

Wrong Directions given find minimum moves so that he can reach to the destination

SAP Hiring Off-Campus General Aptitude

Generate next palindrome number

Find next greater number with same set of digits

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Given a string, find the first character which is non-repetitive

Implement LRU Cache

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

VMWare Openings

Find Pythagorean Triplets in an array in O(N)

Find Nearest Minimum number in left side in O(n)

Print Power Set of a Set

Templates in C++

TicTacToe Game As Asked in Flipkart

How Radix sort works

Sort an array according to the order defined by another array

Copyright © 2025 · Genesis Framework · WordPress · Log in