On-campus company coding question

general
, ,
1

In a campus placement company coding round I got this question. I was not able to solve it. Can anyone help how to solve this problem.
Given a chain connected by links you have to disconnect it in such a way that you can create all lengths chain 1 to N
Here is example
N = 21
1–1--1–1--1–1--1–1--1–1--1–1--1–1--1–1--1–1--1–1--1–1 ( – ==> links)
Now answer is 2.
You can break 2 links such that you get 1,1,3,5,11 After disconnecting you get one link chain.
Answer should be minimum disconnections.

2

Samajh nhi aara aapka sawaal. You mind explaining in a good manner please.

3

I am saying that if you have
1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1
this chain with 21 links after breaking 2 links you get these chains
1,1,3,5,11
Now if you want any chain of length between[1-21] you can get by adding these separate chain
For example
21 length = 1+1+3+5+11
15 length = 11 + 3 + 1
5 length = 5
So with only 2 disconnection you can get all length chains [1-21] or [1-N]

4

  1. By breaking just two links, how did you get 1,1,3,5,11?

  2. If there are 21 links, the chain length must be 22, right?

3 Likes
5

Yeah you are right I thought it about again so here links(–) are representing a chain so when you have this chain with 21 (–) links
1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1
Step 1
Now suppose you disconnect it to get 3 links(–) like this
(1–1–1–1) <==>(–) <==>1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1–1
Mind it when you breaking one link it is breaking from both side so you got 3,1.
Step 2
Now again when you break it to get 5 it will be like this
(1–1–1–1) <==>(–) <==>(1–1–1–1–1–1)<==>(–)<==>(1–1–1–1–1–1–1–1–1–1–1–1)
So now you will get again 1 for disconnecting from both side and 5,11 will be remaining pieces.

Now if you want to get any number of link chain by connecting them between [1-N] we can get it. In our case N=21

I hope I have answered your question

6

This is a standard question, where you are given N and you have to divide it into some parts such that we can get all number between 1 to N using those parts.
The answer is log2(n)+1
idk how you are getting 2? Answer should be 5?

7

I got this question on hackerearth for 100 points which was maximum points question out of 3 questions (so I don’t think it will be that easy as time constraint was also 2 sec) and only one sample case was there which I have explained in which answer was 2.

9

Now since you can disconnect from both directions the answer will be (log2(n)+1)/2
Proof:
Lets get into binary representation
So we know 1 --> 1 and 2 --> 10 and 3–>11 and 4–>100, When we are making a new number we are just using the bits behind the numbers except when we reach power of 2 here we need a new set bit, Like

To form 3 we need set bit at 0 and 1 which we have in 2 and 1, to form 5 we need set bit at 2 and 0 which we can find in 1 and 4 and so on
so basically we need to find all the power of 2 till that number.

Like in case of 21 we can take 1,2,4,8,and add remaining that is 6 because we need next power and 6 is smaller than next power so 6. they will make all numbers.

Hence log2(N)+1 and as your questions states the chains can be disconnected from both sides in one move so answer will be (log2(N)+1)/2

Talking about the constraints it’s not always necessary that is 2 secs is given then the solution can’t be small.

Some Examples:

N = 45
Answer: 1 2 4 8 16 14 —> 3
N = 69
Answer: 1 2 4 8 16 32 6 —> 3

You can try checking this logic yourself too. :smiley:

1 Like
10

Yeah thanks mate.
Damm it wasy easy :sob:

1 Like