Brute force — exhaustive search, when acceptable: Question bank

3.7.1 · D5 · Coding › Algorithm Paradigms › Brute force — exhaustive search, when acceptable

Shuru karne se pehle, ek shared vocabulary reminder taaki neeche koi word kamaaye bina na aaye:

Is page par use ki gayi notation (har symbol pehle kamaaya gaya hai)

Neeche ke answers mein kai shorthands aate hain. Kyunki hum inhe use karte hain pehle ki aap inhe kahin aur milen, yahan har ek ko plain words aur ek picture ke saath diya gaya hai.

Ab teen visuals jo reasoning carry karte hain. Har ek neeche ke callout se anchored hai — words padhne se pehle picture dekho.

Figure — Brute force — exhaustive search, when acceptable

True or false — justify

State true/false, then give the reason — a bare verdict scores nothing.

Brute force by definition hamesha ek "clever" algorithm se slower hota hai.

False. Asymptotically slower, lekin ek given constraint ke liye yeh jeet sakta hai:

2^{18} \approx 2.6 \times 1 0^{5}

n = 1 0^{5}

par

O (n^{2})

method ko beat karta hai. Speed growth-rate hai input bound ke relative.

Brute force hamesha correct hota hai.

False as stated — yeh correct hai sirf tabhi jab enumeration complete ho (koi candidate miss na ho) aur verifier correct ho. Ek buggy inner loop jo candidates skip karta hai correctness tod deta hai.

Agar kisi problem ka answer exist karta hai, toh exhaustive search usse dhundh legi.

Sirf tab jab search space finite aur fully enumerated ho. Ek infinite/unbounded space par (jaise saare integers) yeh forever run kar sakta hai aur kabhi "no answer" conclude nahi kar sakta.

Brute force ki cost sirf candidates ki sankhya hai.

False. Cost

= (candidates ki sankhya) \times (ek verify karne ki cost)

. Ek cheap-lagte

2^{n}

enumeration ke saath

O (n)

verify actually

Θ (2^{n} \cdot n)

hai.

Exponential time complexity (

2^{n}

) ka hamesha matlab hai algorithm unusable hai.

False. Usability diye gaye

n

par depend karti hai.

n \leq 20

ke liye,

2^{n} \approx 1 0^{6}

trivially fast hai; "exponential = forbidden" ek myth hai jo constraint ignore karta hai.

O (n^{2})

brute force hamesha safe hai kyunki polynomial time "efficient" hai.

False.

n = 1 0^{5}

par,

n^{2} = 1 0^{10}

ops

\sim 1 0^{8}

/sec budget se bahut zyada ho jaata hai. Polynomial automatically scale par fast nahi hoti — dekho Time Complexity & Big-O.

Brute force aur backtracking ek hi cheez hai.

False. Backtracking ek exhaustive search hai lekin yeh dead branches ko jaldi prune karta hai; pure brute force har candidate ko bina kisi pruning ke generate karta hai. Dekho Backtracking.

Subset-search brute force ke liye, masks ki sankhya item weights ya values par depend karti hai.

False. Yeh sirf

n

par depend karti hai: unke andar ke numbers chahe kuch bhi ho

2^{n}

subsets hain. Values/weights verification ko affect karte hain, enumeration size ko nahi.

n

items ke saare permutations aur saare subsets enumerate karna same cost karti hai.

False. Subsets

= 2^{n}

, permutations

= n!

n = 12

ke liye:

2^{12} = 4096

12! \approx 4.8 \times 1 0^{8}

— permutations kaafi tezi se explode karte hain.

Brute force hamesha kam memory use karta hai kyunki yeh "bas cheezein try karta hai".

False. Memory is par depend karti hai ki aap kaise enumerate karte ho: masks par iterative loop

O (1)

extra space leta hai, lekin recursive permutation/subset generator

O (n)

depth ka call stack rakhta hai, aur saare candidates ko list mein materialize karna

O (2^{n})

O (n!)

space leta hai — aksar asli bottleneck.

Agar brute force timeout ho, toh problem NP-hard honi chahiye.

False. Timeout ka matlab sirf yeh hai ki aapka enumeration budget ke liye bahut bada hai; ek smarter polynomial algorithm (greedy, DP, hashing) abhi bhi exist kar sakta hai. Hardness ek alag claim hai — dekho NP-Hard Problems.

Spot the error

Har line ek flawed reasoning ya code describe karta hai. Reveal bug ka naam aur fix batata hai. (Parent note ke subset-sum example se yaad karo: W weight cap hai — maximum total weight jo chosen subset ka ho sakta hai — aur wt current subset ka running total weight hai.)

for i in range(n): for j in range(n): check pair (i,j) — saare pairs correctly enumerate karta hai.

Error: yeh double-count karta hai (

(i, j)

aur

(j, i)

dono visit karta hai) aur self-pairs

(i, i)

include karta hai. Fix: inner loop range(i+1, n) distinct unordered pairs ke liye.

Subset-sum solver mein, best = max(best, val) wt <= W check se pehle rakha gaya hai (yahan wt = subset ka total weight, W = allowed weight cap).

Error: yeh infeasible subsets ko score karta hai jinka total weight wt cap W se zyada hai, ek illegal answer return karta hai. Fix: pehle feasibility verify karo (wt <= W), phir best update karo.

"PIN mein 4 digits hain, toh

4^{10}

candidates try karne hain."

Error: base aur exponent swap ho gaye hain. Yeh

b^{k} = 1 0^{4}

hai (10 choices per position, 4 positions), na ki

4^{10}

n \leq 24

ke saath

O (2^{n})

theek hai, aur

2^{24} \approx 1.6 \times 1 0^{7}

hai, toh

n = 40

ke liye

2^{40}

thoda aur zyada hi hai."

Error: exponentials "thoda" scale nahi karte.

2^{40} \approx 1 0^{12}

— roughly 65000 guna bada, budget se kaafi zyada. Har

+ 1

n

kaam ko double kar deta hai.

"Main brute-force karoonga candidates try karke jab tak better wale milte rahen, phir jaldi quit kar lunga."

Error: jaldi quit karna completeness tod deta hai. Saare candidates explore kiye bina aap baad wala better/sirf-valid-wala miss kar sakte ho. Pure brute force ko poora space check karna chahiye (sirf provably safe pruning allowed hai — woh backtracking hai).

"Mera verifier kabhi kabhi ek valid candidate reject karta hai, lekin enumeration complete hai, toh search correct hai."

Error: correctness ke liye dono halves chahiye. Ek galat verifier sahi answer ko reject kar sakta hai chahe use enumerate kiya gaya ho — answer examine hota hai lekin galat tarike se discard ho jaata hai.

"range(1 << n) aur range(2 * n) subsets enumerate karne ke liye same loop hain."

Error: 1 << n equals

2^{n}

(doubling per shift), jabki 2 * n sirf

n

ka double hai.

n = 10

ke liye yeh

1024

20

hai — doosra almost har subset skip karta hai, toh enumeration grossly incomplete hai.

Feasibility estimate: "search space

2^{n}

hai

n = 30

ke saath, aur

2^{30} \approx 1 0^{9}

hai, toh theek hai."

Error:

1 0^{9}

already timeout line par/uske upar hai (

\sim 1 0^{8}

–

1 0^{9}

ops/sec), aur per-candidate verify cost ise aur multiply karti hai. Yeh safely theek nahi hai.

Why questions

Pair search ka inner loop 0 ki jagah i+1 se kyun start karte hain?

Taaki har unordered pair exactly ek baar enumerate ho aur self-pairs skip ho — yeh enumeration ko duplicate-free banata hai,

n^{2}

ki jagah

(2 n)

candidates deta hai.

range(1 << n) exactly

2^{n}

values par iterate kyun karta hai?

Kyunki 1 << n, 1 ke single bit ko

n

baar left shift karta hai, har shift par doubling, toh yeh

2^{n}

equals karta hai — exactly woh subset count jo figure s01 mein hai.

Brute force ko faster algorithms test karne ke liye "reference" ke roop mein kyun use kiya jaata hai?

Kyunki iske correctness par trivially trust karna aasaan hai (complete enumeration + simple verify), toh iska output ek ground truth hai jis se optimized solution ko chhote inputs par compare kiya jaata hai (differential testing).

Har element ka "in or out" contribute karna exactly

2^{n}

subsets kyun deta hai?

n

choices independent hain aur har ek ke 2 options hain, toh total

= n 2 \times 2 \times \dots \times 2 = 2^{n}

multiplication principle se (dekho figure s01).

Wohi multiplication principle permutations ke liye

2^{n}

nahi balki

n!

kyun deta hai?

Subsets ke liye har item mein fixed 2 choices hain; orderings ke liye choice-count har slot par ek se ghadta hai (

n, n - 1, \dots, 1

) kyunki already placed items reuse nahi ho sakte, aur

n \times (n - 1) \times \dots \times 1 = n!

Hum candidate-count ko verify-cost se add kyun nahi karte, multiply kyun karte hain?

Kyunki verifier har candidate ke liye ek baar run hota hai; yeh ek nested cost hai. Total work = candidates

\times

work-per-candidate, jo multiply karta hai.

Iterative brute force memory-cheap kyun ho sakta hai jabki recursive brute force nahi?

Ek iterative mask loop sirf kuch counters rakhta hai (

O (1)

space), lekin recursion har depth level par ek frame stack karta hai,

O (n)

stack space costing — aur saare candidates store karna

O (2^{n})

O (n!)

memory leta hai.

1 0^{8}

feasibility ke liye rough "line in the sand" kyun hai?

Ek typical machine roughly

1 0^{8}

simple operations per second karta hai, toh uske paas ya usse zyada search per-test time budget exceed karne ka risk leta hai. Dekho Time Complexity & Big-O.

Bitmasks subsets enumerate kyun kar sakte hain?

0

2^{n} - 1

tak ek integer ke

n

bits hote hain; bit

i

ko "item

i

chosen?" padhna har integer ko exactly ek distinct subset se correspond karta hai — ek perfect, gap-free enumeration (dekho figure s02). Dekho Bitmasking.

Brute force jaanna abhi bhi kyun matter karta hai agar hum DP ya greedy use karna plan kar rahe hain?

Yeh woh baseline hai jis se har clever method judge ki jaati hai ("brute force se kitna faster?"), aur yeh correct reference deta hai optimized version validate karne ke liye. Dekho Dynamic Programming aur Greedy Algorithms.

Ek short PIN brute force ko devastating kyun banata hai na ki ek defense?

Iska search space

1 0^{4}

tiny hai, toh har PIN try karna instant hai — jo smallness brute force feasible banati hai wahi exactly short secrets ko weak banati hai.

Edge cases

n = 0

(empty item set) ke saath Brute-force subset search — kitne candidates?

Exactly

2^{0} = 1

: sirf ek empty subset. Loop range(1 << 0) = range(1) ek baar mask=0 ke saath run karta hai (kyunki 1 << 0 = 1), correctly "kuch nahi lo" consider karta hai.

Length

n = 1

ke array par Two-sum brute force — kya hota hai?

Zero pairs exist karte hain (

(2 1) = 0

); inner loop kabhi run nahi karta aur function "no answer" return karta hai — sahi result, kyunki ek valid pair ko do distinct indices chahiye.

n = 0

(empty item set) ke saath Permutation brute force — kitne candidates?

Exactly

0! = 1

: kuch bhi nahi ka ek arrangement hai, empty ordering. Yeh subsets ke liye

2^{0} = 1

ko mirror karta hai — "do nothing" case hamesha ek valid candidate hai, kabhi zero nahi.

Subset-sum jahan har item ka weight pehle se hi cap W se zyada hai.

Sirf empty subset (mask=0, weight 0) feasible hai, toh best apni initial value

0

par rehta hai. Algorithm correctly 0 return karta hai, koi infeasible pick nahi.

PIN cracker jab correct PIN 0000 hai.

Loop pin=0 se start karta hai, formatted f"{pin:04d}" = "0000", toh yeh pehla candidate test hota hai — immediately mil jaata hai. :04d zero-padding essential hai ya 0 "0000" valid 4-digit PIN ki jagah "0" print ho jaata.

Ek search space jo infinite hai (jaise "koi bhi real number dhundo jisme property P ho").

Pure brute force applicable nahi hai — aap ek infinite set ko exactly ek baar enumerate nahi kar sakte. Aapko ek finite discretization ya smarter method chahiye; exhaustive search ek finite candidate list assume karta hai.

n = 1

ke saath Permutation brute force.

Exactly

1! = 1

permutation (single item ek order mein). Degenerate lekin

n!

ke consistent; base case formula ko kabhi nahi todta.

Memory blow-up:

n = 12

ke saare permutations ko check karne se pehle list mein materialize karna.

Woh

12! \approx 4.8 \times 1 0^{8}

orderings store karta hai — gigabytes of RAM, likely crash. Fix: candidates ko ek ek karke stream karo (generate-check-discard) taaki space

O (n!)

ki jagah

O (n)

rahe.

Feasibility jab candidate count chhota hai lekin verify expensive hai, jaise

1 0^{3}

candidates har ek ko

n = 1 0^{4}

par

O (n^{2})

check chahiye.

Total

\approx 1 0^{3} \times 1 0^{8} = 1 0^{11}

— infeasible. Chhota candidate count safety guarantee nahi karta; hamesha verify cost se multiply karo.

Recall Jaane se pehle self-check

Ek aisa case dein jahan ek "exponential" brute force ek "polynomial" wale ko beat kare.
Kis single line ne $n^{2}$ ordered pairs ko $(2 n)$ unordered ones mein turn kiya?
Woh do conditions naam batao jo milkar brute force ko correct banati hain.
1 << n $2^{n}$ ke barabar kyun hai, aur yeh code mein kahan aata hai?
Brute force kaafi memory kab leta hai, sirf time nahi?