Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalar Universititeti Mavzu: Ma’lumotlar tuzilmasi va algoritmlar. Bajardi: Azimov Bahrom Tekshirdi: Bohodir Sharipov

Muhammad al-Xorazmiy nomidagi
Toshkent Axborot Texnologiyalar
Universititeti

Mavzu: Ma’lumotlar tuzilmasi va algoritmlar.
Bajardi: Azimov Bahrom
Tekshirdi: Bohodir Sharipov

Toshkent 2022

1-masala
Tartibga solinmagan butun sonlar qatori berilgan bo'lsa, eng kichik etishmayotgan musbat sonni qaytaring.
Siz O(n) vaqtida ishlaydigan va doimiy qo'shimcha joydan foydalanadigan algoritmni amalga oshirishingiz kerak.

public class Solution {

public int FirstMissingPositive(int[] nums) {
if (nums.Length == 1 && nums[0] == 1) return 2;
else if (nums.Length == 1 && nums[0] != 1) return 1;

Array.Sort(nums);

int i = 0;
int lowest = int.MaxValue;
for (; i < nums.Length - 1; i++) {
// ignore negative numbers
if (nums[i] < 0) continue;

// save lowest number

if (nums[i] < lowest) lowest = nums[i];

// checks for if the numbers are one after the other

if (nums[i] + 1 == nums[i + 1] || nums[i] == nums[i + 1]) continue;

// if they aren't return based on the lowest number

return lowest == 1 || lowest + 1 == 1 ? nums[i] + 1 : 1;
}
// return based on the lowest number if nothing
// was returned during the loop
return lowest == 1 || lowest + 1 == 1 || nums[i] == 1 ? nums[i] + 1 : 1;
}
}

2-maslala
n butun son berilgan bo'lsa, yig'indisi n ga teng bo'lgan eng kam mukammal kvadrat sonlarni qaytaring.
Mukammal kvadrat - bu butun sonning kvadrati bo'lgan butun son; boshqacha qilib aytganda, u o'zi bilan qandaydir butun sonning ko'paytmasidir. Masalan, 1, 4, 9 va 16 mukammal kvadratlar, 3 va 11 esa emas.

public class Solution {
public int NumSquares(int n) {
int[] d = new int[n + 1];

for(int i = 1; i <= n; i++)

{
d[i] = int.MaxValue;

for(int j = 1; j * j <= i; j++)

{
d[i] = Math.Min(d[i], d[i - j * j] + 1);
}
}

return d[n];

}
}