Problem Çözme Stratejileri

package main

import "fmt"

// Örnek problem: "Bir dizide toplamı hedefe eşit iki eleman var mı?"
//
// SORULAR:
//   - Dizi sıralı mı?           → hayır, varsayalım sırasız
//   - Aynı eleman iki kez?      → hayır, farklı indeksler
//   - Negatif sayı olabilir mi? → evet
//   - Boş dizi?                 → cevap: yok
//   - Birden çok çift varsa?    → herhangi biri yeterli

// Elle çalışma:
//   dizi = [2, 7, 11, 15], hedef = 9
//   2 + 7 = 9  ✓  → indeksler (0, 1)
//
//   dizi = [3, 3], hedef = 6
//   3 + 3 = 6  ✓  → indeksler (0, 1)  ← tekrarlı değerler sorun değil
//
//   dizi = [1, 2], hedef = 100
//   yok

func twoSum(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int, len(nums)) // değer → indeks
	for i, v := range nums {
		if j, ok := seen[target-v]; ok {
			return j, i, true
		}
		seen[v] = i
	}
	return 0, 0, false
}

func main() {
	cases := []struct {
		nums   []int
		target int
	}{
		{[]int{2, 7, 11, 15}, 9},
		{[]int{3, 3}, 6},
		{[]int{1, 2}, 100},
		{[]int{}, 0},
		{[]int{-3, 4, 3, 90}, 0},
		{[]int{5}, 5},
	}

	for _, c := range cases {
		i, j, ok := twoSum(c.nums, c.target)
		if !ok {
			fmt.Printf("%-18v hedef=%-5d → bulunamadı\n", c.nums, c.target)
			continue
		}
		fmt.Printf("%-18v hedef=%-5d → indeks (%d,%d), değerler %d+%d\n",
			c.nums, c.target, i, j, c.nums[i], c.nums[j])
	}

	fmt.Println()
	fmt.Println("Son iki durum, elle çalışmadan düşünülmesi kolay atlanan kenar durumlar:")
	fmt.Println("  boş dizi ve tek elemanlı dizi")
}

package main

import "fmt"

func main() {
	const opsPerSecond = 100_000_000 // ~10^8

	complexities := []struct {
		name string
		calc func(n int) float64
	}{
		{"O(log n)", func(n int) float64 { return log2(n) }},
		{"O(n)", func(n int) float64 { return float64(n) }},
		{"O(n log n)", func(n int) float64 { return float64(n) * log2(n) }},
		{"O(n²)", func(n int) float64 { return float64(n) * float64(n) }},
		{"O(n³)", func(n int) float64 { return float64(n) * float64(n) * float64(n) }},
		{"O(2^n)", func(n int) float64 {
			if n > 60 {
				return 1e30
			}
			return pow2(n)
		}},
	}

	sizes := []int{10, 100, 1_000, 100_000, 1_000_000}

	fmt.Printf("%-12s", "karmaşıklık")
	for _, n := range sizes {
		fmt.Printf("%14s", fmt.Sprint("n=", n))
	}
	fmt.Println()

	for _, c := range complexities {
		fmt.Printf("%-12s", c.name)
		for _, n := range sizes {
			ops := c.calc(n)
			seconds := ops / opsPerSecond
			fmt.Printf("%14s", format(seconds))
		}
		fmt.Println()
	}

	fmt.Println()
	fmt.Println("Okuma: 'anlık' = ihmal edilebilir, 'ÇOK UZUN' = pratik değil")
	fmt.Println()
	fmt.Println("Pratik kural: yarışma ve mülakatlarda süre sınırı genelde 1-2 saniyedir.")
	fmt.Println("Kısıta bakıp hedef karmaşıklığı belirle, sonra o karmaşıklıkta çözüm ara.")
}

func log2(n int) float64 {
	count := 0.0
	for n > 1 {
		n /= 2
		count++
	}
	return count
}

func pow2(n int) float64 {
	result := 1.0
	for range n {
		result *= 2
	}
	return result
}

func format(seconds float64) string {
	switch {
	case seconds < 0.001:
		return "anlık"
	case seconds < 1:
		return fmt.Sprintf("%.0f ms", seconds*1000)
	case seconds < 60:
		return fmt.Sprintf("%.1f sn", seconds)
	case seconds < 3600:
		return fmt.Sprintf("%.0f dk", seconds/60)
	case seconds < 86400*365:
		return fmt.Sprintf("%.0f gün", seconds/86400)
	default:
		return "ÇOK UZUN"
	}
}

package main

import "fmt"

// PROBLEM: Bir dizide, toplamı en büyük olan bitişik alt diziyi bul.

// ADIM 1 — KABA KUVVET: tüm alt dizileri dene
// O(n³): her başlangıç, her bitiş, her toplam
func bruteForce(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	best := nums[0]
	for i := range nums {
		for j := i; j < len(nums); j++ {
			sum := 0
			for k := i; k <= j; k++ {
				sum += nums[k]
			}
			best = max(best, sum)
		}
	}
	return best
}

// ADIM 2 — TEKRAR EDEN İŞİ ORTADAN KALDIR: toplamı artımlı hesapla
// O(n²)
func improved(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	best := nums[0]
	for i := range nums {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j] // önceki toplamı yeniden kullan
			best = max(best, sum)
		}
	}
	return best
}

// ADIM 3 — YAPIYI FARK ET: "buraya kadarki en iyi" bilgisini taşı
// O(n) — Kadane algoritması
func optimal(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	best, current := nums[0], nums[0]
	for _, v := range nums[1:] {
		// Ya yeni baştan başla ya mevcut diziyi genişlet
		current = max(v, current+v)
		best = max(best, current)
	}
	return best
}

func main() {
	cases := [][]int{
		{-2, 1, -3, 4, -1, 2, 1, -5, 4},
		{1, 2, 3},
		{-5, -2, -8},
		{5},
		{},
	}

	fmt.Printf("%-32s %10s %10s %10s %8s\n", "dizi", "O(n³)", "O(n²)", "O(n)", "aynı")
	for _, c := range cases {
		a, b, d := bruteForce(c), improved(c), optimal(c)
		fmt.Printf("%-32v %10d %10d %10d %8t\n", c, a, b, d, a == b && b == d)
	}

	// Büyük girdide fark
	fmt.Println()
	n := 3000
	big := make([]int, n)
	for i := range big {
		big[i] = (i*7919)%201 - 100 // deterministik, negatifler dâhil
	}

	fmt.Printf("n=%d için üç çözümün sonucu:\n", n)
	fmt.Println("  O(n³):", bruteForce(big[:300]), "(yalnızca 300 eleman, tamamı çok yavaş olurdu)")
	fmt.Println("  O(n²):", improved(big))
	fmt.Println("  O(n): ", optimal(big))

	fmt.Println()
	fmt.Println("İşlem sayısı tahmini (n=3000):")
	fmt.Println("  O(n³) ≈", 3000*3000*3000/1_000_000, "milyon işlem → dakikalar")
	fmt.Println("  O(n²) ≈", 3000*3000/1_000_000, "milyon işlem → anlık")
	fmt.Println("  O(n)  ≈", 3000, "işlem → ölçülemez")

	fmt.Println()
	fmt.Println("STRATEJİ: Kaba kuvvetten optimal çözüme giden yol")
	fmt.Println("  1. Çalışan bir çözüm yaz (doğruluğu garanti et)")
	fmt.Println("  2. Tekrar eden işi bul ve ortadan kaldır")
	fmt.Println("  3. Problemin yapısal özelliğini keşfet")
	fmt.Println("  4. Her adımda önceki çözümle karşılaştırarak doğrula")
}

package main

import (
	"fmt"
	"math/rand/v2"
	"slices"
)

// Test edilecek fonksiyon: sıralı diziden tekrarları temizle
func dedup(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	write := 1
	for read := 1; read < len(nums); read++ {
		if nums[read] != nums[write-1] {
			nums[write] = nums[read]
			write++
		}
	}
	return nums[:write]
}

// Referans uygulama: yavaş ama kesin doğru
func dedupReference(nums []int) []int {
	var out []int
	for _, v := range nums {
		if len(out) == 0 || out[len(out)-1] != v {
			out = append(out, v)
		}
	}
	return out
}

func main() {
	// 1) Elle seçilmiş kenar durumları
	edgeCases := []struct {
		name string
		in   []int
	}{
		{"boş", []int{}},
		{"tek eleman", []int{5}},
		{"iki aynı", []int{3, 3}},
		{"iki farklı", []int{1, 2}},
		{"hepsi aynı", []int{7, 7, 7, 7}},
		{"tekrarsız", []int{1, 2, 3, 4}},
		{"karışık", []int{1, 1, 2, 3, 3, 3, 4}},
		{"negatifler", []int{-5, -5, 0, 0, 3}},
	}

	fmt.Printf("%-14s %-24s %-20s %8s\n", "durum", "girdi", "çıktı", "doğru")
	allPass := true
	for _, tc := range edgeCases {
		input := slices.Clone(tc.in)
		want := dedupReference(tc.in)
		got := dedup(input)
		ok := slices.Equal(got, want)
		if !ok {
			allPass = false
		}
		fmt.Printf("%-14s %-24v %-20v %8t\n", tc.name, tc.in, got, ok)
	}
	fmt.Println("tüm kenar durumları geçti:", allPass)

	// 2) Rastgele test: referansla karşılaştır (sabit tohum → deterministik)
	fmt.Println()
	r := rand.New(rand.NewPCG(42, 1024))
	failures := 0
	const trials = 2000

	for range trials {
		n := r.IntN(15)
		input := make([]int, n)
		for i := range input {
			input[i] = r.IntN(6) // küçük aralık: çok tekrar olsun
		}
		slices.Sort(input)

		want := dedupReference(input)
		got := dedup(slices.Clone(input))
		if !slices.Equal(got, want) {
			failures++
			if failures == 1 {
				fmt.Println("  ilk hata:", input, "→", got, "beklenen", want)
			}
		}
	}
	fmt.Printf("%d rastgele testten %d tanesi başarısız\n", trials, failures)

	// 3) Değişmez kontrolü
	fmt.Println()
	fmt.Println("değişmezler:")
	test := []int{1, 1, 2, 2, 3}
	result := dedup(slices.Clone(test))
	fmt.Println("  sonuç sıralı mı:", slices.IsSorted(result))
	fmt.Println("  tekrar kalmadı mı:", len(result) == len(slices.Compact(slices.Clone(test))))
	fmt.Println("  uzunluk azaldı mı:", len(result) <= len(test))
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// Yarışma problemleri için standart hızlı giriş/çıkış iskeleti
func main() {
	// Bu örnek, gerçek stdin yerine bir metinden okuyor;
	// gerçek kullanımda os.Stdin kullanılır.
	input := `5
3 1 4 1 5
merhaba dünya
7 8
`
	reader := bufio.NewReaderSize(strings.NewReader(input), 1<<16)
	writer := bufio.NewWriterSize(os.Stdout, 1<<16)
	defer writer.Flush() // ÇOK ÖNEMLİ: unutulursa çıktı hiç yazılmaz

	scanner := bufio.NewScanner(reader)
	scanner.Buffer(make([]byte, 1<<20), 1<<20) // uzun satırlar için
	scanner.Split(bufio.ScanWords)             // kelime kelime oku

	readInt := func() int {
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		return n
	}
	readString := func() string {
		scanner.Scan()
		return scanner.Text()
	}

	// Girdiyi oku
	n := readInt()
	nums := make([]int, n)
	for i := range nums {
		nums[i] = readInt()
	}
	word1 := readString()
	word2 := readString()
	a, b := readInt(), readInt()

	// İşle ve yaz
	sum := 0
	for _, v := range nums {
		sum += v
	}

	fmt.Fprintln(writer, "eleman sayısı:", n)
	fmt.Fprintln(writer, "sayılar:", nums)
	fmt.Fprintln(writer, "toplam:", sum)
	fmt.Fprintf(writer, "kelimeler: %q %q\n", word1, word2)
	fmt.Fprintln(writer, "son iki sayının çarpımı:", a*b)

	// Çok sayıda satır yazarken Fprintln, Println'den kat kat hızlıdır
	fmt.Fprintln(writer, "--- hızlı çıktı örneği ---")
	for i := 1; i <= 5; i++ {
		fmt.Fprintf(writer, "satır %d\n", i)
	}
}

package main

import (
	"fmt"
	"slices"
)

// PROBLEM: Bir dizide, her elemanın kendisi hariç diğer tüm elemanların
// çarpımını içeren yeni bir dizi döndür. Bölme işlemi KULLANMA.
//
// ADIM 1 — ANLAMA
//   girdi:  [1, 2, 3, 4]
//   çıktı:  [24, 12, 8, 6]
//           (2*3*4, 1*3*4, 1*2*4, 1*2*3)
//
//   Sorular: sıfır olabilir mi? → evet
//            negatif? → evet
//            boş/tek eleman? → varsayım: boş dizi döner
//
// ADIM 2 — KISITLARDAN KARMAŞIKLIK
//   n ≤ 10^5 verilmişse O(n²) olmaz (10^10 işlem) → O(n) veya O(n log n) gerekir
//
// ADIM 3 — KABA KUVVET
//   Her eleman için diğerlerini çarp: O(n²)
//
// ADIM 4 — YAPIYI FARK ET
//   Bir elemanın cevabı = (solundakilerin çarpımı) × (sağındakilerin çarpımı)
//   Önek ve sonek çarpımları! → O(n) ve bölme yok

// bruteForce: O(n²) — doğruluk referansı
func bruteForce(nums []int) []int {
	out := make([]int, len(nums))
	for i := range nums {
		product := 1
		for j := range nums {
			if i != j {
				product *= nums[j]
			}
		}
		out[i] = product
	}
	return out
}

// optimal: O(n) zaman, O(1) ek bellek (çıktı hariç)
func optimal(nums []int) []int {
	n := len(nums)
	if n == 0 {
		return nil
	}
	out := make([]int, n)

	// 1. geçiş: out[i] = solundakilerin çarpımı
	prefix := 1
	for i := range nums {
		out[i] = prefix
		prefix *= nums[i]
	}

	// 2. geçiş: sağdan gelen çarpımla birleştir
	suffix := 1
	for i := n - 1; i >= 0; i-- {
		out[i] *= suffix
		suffix *= nums[i]
	}
	return out
}

func main() {
	// ADIM 5 — TEST: kenar durumları
	cases := [][]int{
		{1, 2, 3, 4},
		{2, 3},
		{5},
		{},
		{1, 0, 3},   // bir sıfır
		{0, 0, 3},   // iki sıfır
		{-1, 2, -3}, // negatifler
		{1, 1, 1, 1},
	}

	fmt.Printf("%-20s %-24s %-24s %8s\n", "girdi", "kaba kuvvet", "optimal", "aynı")
	for _, c := range cases {
		a := bruteForce(c)
		b := optimal(c)
		fmt.Printf("%-20v %-24v %-24v %8t\n", c, a, b, slices.Equal(a, b))
	}

	// Büyük girdide doğrulama
	fmt.Println()
	n := 2000
	big := make([]int, n)
	for i := range big {
		big[i] = (i % 3) + 1 // taşmayı önlemek için küçük değerler, ama 0 yok
	}
	a, b := bruteForce(big), optimal(big)
	fmt.Printf("n=%d: iki çözüm aynı mı: %t\n", n, slices.Equal(a, b))
	fmt.Println("  ilk üç değer:", b[:3])

	fmt.Println()
	fmt.Println("ÇÖZÜM SÜRECİ ÖZETİ:")
	fmt.Println("  1. Örnekle çalıştım: [1,2,3,4] → [24,12,8,6]")
	fmt.Println("  2. Kısıta baktım: O(n²) olmaz")
	fmt.Println("  3. Kaba kuvveti yazdım (doğruluk referansı)")
	fmt.Println("  4. Yapıyı fark ettim: sol çarpım × sağ çarpım")
	fmt.Println("  5. Kenar durumlarını test ettim: boş, tek, sıfırlar, negatifler")
	fmt.Println("  6. Kaba kuvvetle karşılaştırarak doğruladım")
}