Master The Art of Problem Solving | Google CodeJam

I discuss a problem from Google CodeJam 2019 Round 1C.

Video Solutions to famous Interview Questions
Use "rachit" as coupon code to get 30% off.

AlgoExpert has video solutions to 65 coding problems, covering all the important topics generally asked in Coding Interviews.

🔥 SUBSCRIBE AND HIT BELL ICON TO CHECK MORE OF MY CONTETNT 🔥

================
Important Playlists:
================
Check my channel for guided content.

MyProgrammingBlog
===============

MyProgrammingProfiles:
===================

[sanyagupta]

We can do it in 148 question only
First we will ask first letter of every word(119) ques . Then we will ask 2nd character of those words whose first character is letter which has appeared only 23 times .(119+23) questions. Then we will ask third letter of those words whose 2nd letter has appeared 5 times only in that 23 words. (119+23+5) ques .Then we will ask 4th letter of those five words(119+23+5+1).Now we can get whole 5 letter word

[scratchtech]

1 simple question - what is the missing permutation?

[yuvarajyuvi]

First we have to 119 question. All the first character should have 24 results. Probably one of them have 23 results. Then take that 23 results and ask for third character. So each will have 6 combinations. Probably one of them have 5. Then take that 5 results and ask for 5 fourth characters. Here each will have 2 combination. Probably one of them have only one. And finally ask one character to find the result..So 119+23+5+1 = 148

[gauravgupta]

We can do it in just asking 5 question.
1) First character of missing word.
2) Second character of missing word.
3) Third character of missing word.
4) Fourth character of missing word.
5) Fifth character of missing word.

Ninja technique.
I just increased my chance to be hired in Facebook. 😎😎

[Abdulmajeed-syus]

119(finds 1st digit of missing number)+23(finds second digit)+5(finds third digit) +1(fourth digit) and if u know first four digit you can find fifth digit

[avineshwar]

A good insight, for sure.


Another O(N) solution would be to simply XOR the available (i.e. 119) permutations and result would be the missing permutation.


I would love to hear more about the power of XOR and how, if at all, to draw problems towards it as well as when to sense out the possibility of using a XOR (or similar) operation.

[shiwanikumari]

First 119 questions+ 23 questions+ 5 questions+1 questions

[narayanchaudhary]

Video was good ...please keep us informed about those kind of competitions. It really helps!!

[raamxD]

Hello @Rachit Jain Would you plz cover the solutions for May long Codechef 2019... They Were pretty good. I would love to know how u approach them. 😀😀

[jayant]

Is there logarithmic insight in this question?
Why cant i ask all the permutation combinations in the first place if its existing in the list or not?

[rohithooda]

Can u please send a link of code implementation of this problem

[sakthim]

I have one doubt in your one video you said x^x=0 to find how many digits are occurring once but what would happen if they give series of numbers in that one number repeat 3, 5, 7.. Times x^x^x=x.that time your logic fails?? Give some explanation??? How you will differentiate this type of problem??

[hurshsingh]

Thanks for the hint rachit solved it in 148 questions -> 5!-1+4!-1+3!-1+2!-1+1!-1 = 148 :)

[bhaskarbhasku]

So we can also ask is first character of the permutation. So for each letter in permutation there will n-1 times the first character coming. for ex. abc so abc acd bac bca cab cba are permutations of abc so i remove acd because there should be 2 permutation for each character in the string i get to know that it was acd. Does this count as valid?

[rajatagrawal]

Hey rachit plz do some codechef chalanges videos so that i can understand your approach plz

[amartyabhattacharya]

Check all and store each index in vector. No of q = 119
Starting with c = 23, rest 24
Check vector of c. No of q = 23
Starting with e = 5, rest 6
Check ce, no of q = 5
Starting with b = 1, rest 2
Check ceb, no of q = 1
Got the last
Other one is missing for sure.
Total q = 119+23+5+1=148

[ITEngineer]

Bro make videos on tree based problems
I am unable to approach it

[parthiv]

It’s like where brackets represents the block of a character.

[harshshah]

Ask 119 questions to get 23 strings with 1st letter c
Ask 23 questions to get 5 strings with 2nd letter e
Ask 5 questions to get 1 string with 3rd letter d
So you conclude that string ceb** is missing
Ask 1 question : 4th position of string cbd**, get it as 'd'
You found that ceb** == cebda and missing string is "cebad"

[siteshp]

Hi Rachit,
Great explanation. But I think the second approach of 150 questions is more intuitive than 378 approach.