🇺🇿 129. Sum Root to Leaf Numbers

🟡 O'rta daraja: 129. Sum Root to Leaf Numbers
👨‍💻 Mening yechimim: Java | 0ms Solution | DFS

Hammaga salom! Kechagi masalaning yechimini ko'rib chiqish vaqti keldi.

👨‍💻 Vazifa
Bizning vazifamiz binar daraxtda ildizidan barglarigacha bo'lgan yo'llardagi raqamlarni son sifatida yozib, ularning yig'indisini topish.

👨‍💻 Yechim
1. sum o'zgaruvchisini e'lon qildim.
2. Asosiy metod ichida sum-ga 0 yozib qo'ydim va traverseBT() rekursiv DFS metodini chaqirdim. Bu metodni daraxtni aylanib chiqish uchun va yig'indini topish uchun ishlatamiz. Ahamiyat bering men raqamlarni yozish uchun StringBuilder-ni ishlatayapman.
3. traverseBT() ichida men ishlatadigan odatiy rekursiv DFS yondashuv bilan foydalandim:
- Rekursiv metod uchun asosiy holatni tekshirdim (node null-ga bo'lganida).
- traverseBT() metodini chap va o'ng tugunlar uchun rekursiv chaqiruv qilish.

Shu ikkita odatiy holat o'rtasida ment yana ikkita harakat bajardim:
- Hozirgi tugunning qiymati bo'lgan raqamni StringBuilder-ga qo'shdim.
- Hozirgi tugun bargligini (bola tugunlari yo'qligi) tekshirdim. Agar hozirgi tugun barg bo'lsa, men StringBuilder-dan String qiymatni olib uni integer-ga aylantiraman va sum-ga qo'shib qo'yaman.

Shu metodning oxirida men StringBuilder-dagi oxirgi raqamni o'chiraman. Shu orqali men tugungacha bo'lgan raqamlarni saqlayman. Bu esa keyingi tugunlar uchun to'g'ri raqamlarning to'g'ri navbatini saqlab boradi.

Rekursiv metod tugashi bilan, asosiy metod ichida sum-ning qiymatini qaytaraman.

Ana shunday.
Omad! ✌️🤓

🇬🇧 268. Missing Number

Hi, guys! I've prepared another interesting problem for you today.

🟢 Easy: 268. Missing Number
👨‍💻 My solution: Java O(N + N) Solution

Good luck! ✌️🤓

🇺🇿 268. Missing Number

Hammaga salom! Yana bitta qiziqarli masala tayyorlab qo'ydim.

🟢 Oson: 268. Missing Number
👨‍💻 Mening yechimim: Java O(N + N) Solution

Vazifamiz - bu yetishmayotgan sonni topish.
Omad! ✌️🤓

🇬🇧 268. Missing Number

🟢 Easy: 268. Missing Number
👨‍💻 My solution: Java O(N + N) Solution

Hi, guys! Before we start, I'd like to mention that we will review several solution for this problem. Let's gooo!

👨‍💻 Task
You are given unsorted numbers from 0 to n, where one number out of this range is missing. You should return the missing one.

💡 Idea
Basically, what I've done is that I take all numbers and put them into Set. Then I go thru all possible numbers from 0 to n and find the number, which is not in this Set.
- Why HashSet?
- Because it keeps only unique elements and method complexity is O(1) in common.

👨‍💻 Solution
1. I create a HashSet.
2. In the first for loop I go thru given numbers and put them to the Set.
3. Then in the second loop I go thru all possible numbers from 0 to n and check if set contains that number. If set does not, then we found our element.

This is it! Keep in mind that I will post other possible solutions in the next posts!
Good luck! ✌️🤓

🇺🇿 268. Missing Number

🟢 Oson: 268. Missing Number
👨‍💻 Mening yechimim: Java O(N + N) Solution

Hammaga salom! Boshlashdan avval aytib o'tmoqchi bo'lgan narsam - berilgan masalaga bir nechta yechimlarni ko'rib chiqamiz. Ketdik!

👨‍💻 Vazifa
Sizga 0-dan n-gacha bo'lgan sonlardan iborat massiv berilgan. Shu massivning ichida bitta son yetishmaydi. Siz shu sonni topishingiz lozim.

💡 G'oya
Mening yechimimning g'oyasi oddiy. Men Set ma'lumotlar tuzilmasini olib, massivdan hamma sonlarni qo'shaman. Keyin 0-dan n-gacha hamma sonni bir-birlab Set-da mavjudligini tekshiraman.
- Nimaga HashSet?
- Chunki Set - bu teng bo'lmagan elementlarni saqlaydi va HashSet-ning metodlarining tezligi odatda O(1).

👨‍💻 Solution
1. HashSet yarataman.
2. Birinchi for loop ichida massivni aylanib chiqib, har bir elementini Set-ga joylashtiraman.
3. Ikkinchi for loop ichida 0-dan n-gacha bo'lgan hamma sonni Set-da mavjudligini bir-birlab tekshirib chiqaman. Agar qaysidir son Set-da mavjud bo'lmasa - biz elementni topdik.

Bugunga shu. Keyingi postlarda boshqa yechimlarni ko'rib chiqamiz.
Omad! ✌️🤓

🇬🇧 268. Missing Number. Arithmetic progression sum.

🟢 Easy: 268. Missing Number
👨‍💻 Example: Java O(N) | 3 Lines | Arithmetic Sum

Hi, guys! Let's check another solution for the problem.

👨‍💻 Task
You are given unsorted numbers from 0 to n, where one number out of this range is missing. You should return the missing one.

💡 Idea
The idea is brilliant. We know that we are given numbers from 0 to n, but one missing. Also, we know the first and the last number in the array.
So, it looks like we can apply arithmetic progression in some way...
Why? Because we know that numbers are in the sequence with the same delta.

If you take the formula of arithmetic progression sum (where we know the last element) it will look like this:

sum = n * (a1 + an) / 2

Where n - number of elements, a1 and an - first and the last elements in the sequence respectively.

This formula will give us the sum with all numbers. And how can we find missing element, knowing the sum of all numbers without missing any?

We should find the actual sum in of elements of array. Then we substract this actual sum from arithmetic sum and we will get the result.

👨‍💻 Solution
1. I create 3 variables to make it readable:
- actualSum - actual sum of the array with missing number.
- an - the last element of the sequence.
- n - number of elements in the progression.
2. Using for loop I run thru the array and sum all the existing elements.
3. I use the formula above to calculate arithmetic progression sum for n elements starting from 0. Then I substract the actualSum and get the answer.

Credits:
I must give credits to active readers who shared similar solutions. These are @sherhonbek_1, @sjavokhir, and @Dilshodbek_Akhmedov.
Congrats! You are on TV! 😁🤜🤛

Good luck! ✌️🤓

🇺🇿 268. Missing Number. Arifmetik progressiya yig'indisi.

🟢 Oson: 268. Missing Number
👨‍💻 Yechim misoli: Java O(N) | 3 Lines | Arithmetic Sum

Hammaga salom! Keling bugun berilgan masalaning boshqa yechimini ko'rib chiqamiz.

👨‍💻 Vazifa
Sizga 0-dan n-gacha bo'lgan sonlardan iborat massiv berilgan. Shu massivning ichida bitta son yetishmaydi. Siz shu sonni topishingiz lozim.

💡 G'oya
Bu yechimning g'oyasi ajoyib. Matematik usul bilan yechamiz. Sizga 0-dan n-gacha sonlar berilgan va ular ichida bittasi mavjud emas. Yana shu ketma-ketlikning birinchi va oxirgi sonini bilasiz.

Agar sonlarni o'sish navbatda joylashtirsangiz, unda ikkita qo'shni sonning farqi bir xil delta ekanligini tushunasiz. Huddi arifmetik progressiyasini ishlatishingiz mumkinligiga o'xshaydi...

Keling arifmetik (oxirgi elementi ma'lum bo'lgan) progressiyaning yig'indisining formulasini ko'ramiz:

sum = n * (a1 + an) / 2

Bu yerda n - elementlar soni, a1 and an - birinchi va oxirgi elementlar.

Bu formula sizga 0-dan n-gacha bo'lgan hamma sonlarning yig'indisini beradi. Endi savol: qanday qilib shu narsalarni bila turib, siz massivdan yetmaydigan sonni topishingiz mumkin?

Siz massivdagi elementlarning yig'indisini topishingiz lozim. Keyin siz massivning yig'indisini arifmetik progressiyaning yig'indisidan ayrishingiz lozim. Shu farq - bu massivda mavjud bo'lmagan sondir.

👨‍💻 Yechim
1. Men oson tushunish uchun uchta o'zgaruvchi yaratdim:
- actualSum - massiv elementlarining yig'indisi.
- an - progressiyaning oxirgi elementi.
- n - progressiyadagi elementlarning soni.
2. for loop-dan foydalanib, massiv elementlarining yig'indisini topaman.
3. Tepadagi formulani ishlatib, arifmetik progressiyaning yig'indisini topaman va massiv elementlarining yig'indisini ayrib qo'yaman. Natijada yetmayotgan son kelib chiqadi va uni qaytaramiz.

Credits:
Aktiv va o'zining yechimlari bilan bo'lishgan obunachilarga rahmat aytaman. Bular @sherhonbek_1, @sjavokhir va @Dilshodbek_Akhmedov.
Tabriklayman, sizlar televizorda chiqdingizlar! 😁🤜🤛

Omad! ✌️🤓

🇬🇧 268. Missing Number. Using Another Array.

🟢 Easy: 268. Missing Number
👨‍💻 Solution: Efficient solution || 2 Methods || Simple

Hi, guys! Let's check out one interesting solution from LeetCode user Kunal_Jain21. The link to the solution is above.

👨‍💻 Task
You are given unsorted numbers from 0 to n, where one number out of this range is missing. You should return the missing one.

💡 Idea
Again the idea is cool. Since we know that one number is missing, we can create another array with n + 1 length, where n - length of given array. Then we can run thru all given numbers and using some kind of tag. As a result, in the second array the element which will not have a tag, will be the answer. Simple!

👨‍💻 Solution
1. You need to create new array temp with length of length + 1.
2. Inside for loop take elements from given array nums and use them as indices for temp. Assign 1 to that elements of temp array.
3. Inside for loop [for length + 1 elements] check if an element of temp equals 0, since integers arrays are initialized with default 0's, which means that the element under this index does not have a tag [or is not changed]. Return this index.

This is it!
Good luck! ✌️🤓

🇬🇧 268. Missing Number. Ikkinchi massiv ishlatish.

🟢 Oson: 268. Missing Number
👨‍💻 Yechim: Efficient solution || 2 Methods || Simple

Salom! Bugun yana bitta qiziqarli va noyob yechimni ko'rib chiqaman. Bu yechimni Kunal_Jain21 user post qilgan. Yechimga havolani tepada qoldirganman.

👨‍💻 Vazifa
Sizga 0-dan n-gacha bo'lgan sonlardan iborat massiv berilgan. Shu massivning ichida bitta son yetishmaydi. Siz shu sonni topishingiz lozim.

💡 G'oya
Bu yechim ham juda oddiy va ajoyib. Bilasiz, berilgan massivdan [0-dan n-gacha] bitta son olib tashlangan. Agar massivning uzunligi n bo'lsa, siz n + 1 uzunlikka ega ikkinchi massivni yaratasiz. Keyin birinchi massivning hamma elementlari aro yurib chiqasiz va mavjud bo'lgan sonlarga teg qo'yib chiqasiz. Natijada, ikkinchi massivda tegi bo'lmagan element siz qidirayotgan javob bo'ladi.

👨‍💻 Yechim
1. Siz ikkinchi n + 1 uzunlikka ega temp massivini yaratasiz.
2. Birinchi for loop ichida birinchi massivning elementlarini ikkinchi massivning indekslari sifatida ishlatib, mavjud bo'lgan sonlarni 1 bilan belgilab qo'yasiz.
3. Ikkinchi for loop ichida ikkinchi massivning elementlarini 0ga tengligini tekshirasiz. Agar i indeksli element 0ga teng bo'lsa, demak sizning javobingiz shu indeks bo'ladi.
- Nimaga?
- Birinchidan, yaratilgan array 0-lar bilan to'ldiriladi. Ikkinchidan, birinchi for loop-da bitta indeksdan tashqari hamma indeks 1 bilan belgilaniladi. Natijada, 0ga teng bo'lgan elementning indeksi - siz qidirayotgan javob :).

Bugunga shu!
Omad! ✌️🤓

🇬🇧 It seems like the channel gets monotonic. Why not to have some fun?😀

🇺🇿 Kanal bir xil postlardan iborat bo'lgani uchun zerikarli bo'lishi mumkin. Ozgina hazillar ham bo'lsin.😀

🇬🇧 268. Missing Number. Using sort().

🟢 Easy: 268. Missing Number
👨‍💻 Solution: Java || Simple Solution

Hi! Let's check out one more solution based on sorting. This solution is written by user Primordial_Black. Give him appreciations by going and checking his solution. The link is provided above.

👨‍💻 Task
You are given unsorted numbers from 0 to n, where one number out of this range is missing. You should return the missing one.

💡 Idea
The idea is to sort given array. You will have a sorted array with missing number from sequence 0...n. Then this user takes max element and starts checking elements from the end of the array.

👨‍💻 Solution
1. First, you need to sort your array.
2. Create max variable and assign max value from sequence.
3. Then check if max is equal to the length of the array. If yes, we skip the expression inside if block. If no, we return the length of given array. Why? Think about this and write in the comments below.
4. Then there is a for loop which starts from pre-last element and goes backwards.
- We check if current element with index i is equal to max - 1. If it is, then it means this is not missing number and we decrease the max.
- Else if current element is not equal to max - 1 it means that we've found that number [because difference is not 1] and return max - 1.

This is it. What do you think how many solutions left? 😁
Good luck! ✌️🤓

🇺🇿 268. Missing Number. sort() ishlatgan holda.

🟢 Oson: 268. Missing Number
👨‍💻 Yechim: Java || Simple Solution

Hammaga salom! Keling bugun yana bitta sort() metodi ishlatilgan yechimni ko'rib chiqamiz. Bu yechimni Primordial_Black user yozgan ekan. Shu yechimni LeetCode saytining o'ziga kirib tekshiring, yoqsa - like bosing. Bu orqali dasturchiga hurmat va minnatdorchilik bildirgan bo'lasiz. Uning yechimiga havolani tepada qoldirganman.

👨‍💻 Vazifa
Sizga 0-dan n-gacha bo'lgan sonlardan iborat massiv berilgan. Shu massivning ichida bitta son yetishmaydi. Siz shu sonni topishingiz lozim.

💡 G'oya
Asosiy g'oya - bu massivdagi elementlarni o'sish navbatida joylashtirishdir (sorting). Keyin siz max elementni olib massivning oxiridan boshlab har bir elementni tekshirasiz.

👨‍💻 Yechim
1. Boshida massivni sort qilasiz.
2. Keyin max o'zgaruvchisini yaratasiz va uning qiymatini massivning oxirgi (maksimal) elementiga teng qilasiz.
3. Agar shu max massivning uzunligiga teng bo'lsa, o'tib ketaverasiz, aksincha - massivning uzunligini qaytarasiz. Nimagami? Fikringizni postning tagida comments-da yozing.
4. Keyin esa for loop orqali oxiridan bitta oldin turgan elementdan boshlab, boshigacha elementlarni tekshirib chiqasiz.
- Agar hozirgi (i indeksga ega bo'lgan) element max - 1 ga teng bo'lsa, bu element o'z joyida turgan bo'ladi. max qiymatini 1ga kamaytirasiz.
- Agar element max - 1 ga teng bo'lmasa, siz yetmayotgan sonni topgan bo'lasiz, chunki sonlar farqi 1ga teng emas, va max - 1 ni qaytarasiz.

Bugunga shu. Yana nechta yechim qoldi deb o'ylaysiz? 😁
Omad! ✌️🤓

🇬🇧 268. Missing Number. Using sort() v2.

🟢 Easy: 268. Missing Number
👨‍💻 My solution: Java Interesting Solution

Hi! Yeah, that's again Missing number problem with one more possible solution! :)

👨‍💻 Task
You are given unsorted numbers from 0 to n, where one number out of this range is missing. You should return the missing one.

💡 Idea
The idea of this solution popped up in my mind yesterday while I was writing previous posts. Again the idea is to sort the array, but this time I won't introduce extra variable. I'll use the sorted array and compare elements to their indices.

👨‍💻 Solution
1. You need to sort given array.
2. Then you run thru all elements and compare them to their indices.
- In case an element is not equal to its index, you just return that index. Why? Think about it.
- If an element is equal to its index, then we continue.
3. If all elements equal to their indices and you finish the loop, then it means that you are missing the last number from the sequence, i.e. a number equal to the length of the given array.

That's it. I hope you like the solution.
Cheers! ✌️🤓

🇺🇿 268. Missing Number. sort() ishlatgan holda, v2.

🟢 Oson: 268. Missing Number
👨‍💻 Yechim: Java Interesting Solution

Salom! Bugun yana shu masala va sorting ishlatiladigan yechim! :)

👨‍💻 Vazifa
Sizga 0-dan n-gacha bo'lgan sonlardan iborat massiv berilgan. Shu massivning ichida bitta son yetishmaydi. Siz shu sonni topishingiz lozim.

💡 G'oya
Kecha sort()-lik yechim haqida post yozayotganimda, bugungi yechim hayolimga kelgan edi. Bu variantda ham sort() metodini ishlatasiz, lekin bu safar siz yangi o'zgaruvchi ishlatmaysiz. Faqatgina massiv va uning indekslari kerak bo'ladi.

👨‍💻 Yechim
1. Massivni sort qilasiz.
2. Keying hamma elementni aylanib chiqasiz va ularni indekslariga solishtirasiz.
- Agar element o'z indeksiga teng bo'lmasa, demak indeksni o'zini qaytarasiz xolos. Nimaga deysizmi? O'ylab ko'rib, javobini comments-ga yozing :).
- Agar element o'z indeksiga teng bo'lsa, biz keyingi elementga o'tamiz.
3. Agar hamma element o'z indekslariga teng bo'lib, loop to'liq bajarilsa, bu degani ketma-ketlikdan olib tashlangan son - bu shu ketma-ketlikning oxirgi soni. Boshqa so'z bilan aytganda, massivning uzunligiga teng sondir.

Ana shu xolos. Sizga yechim yoqdi degan umiddaman.
Omad! ✌️🤓