It is a particular way to store and organize data in a computer so that it can be used efficiently. The data structure can be classified into two ways:

  1. Linear data structure
  2. Non-linear data structure

Abstract Data Types

User defined data structures combined with their operations are called Abstract Data types. It consists of two parts:
1. Declaration of data
2. Declaration of operations

Algorithm

The two criteria for algorithms:
1. Correctness — Does the algorithm give solution in finite number of steps?
2. Efficiency — Resources needed in terms of memory and time.
Comparison of Algorithm: Rate of growth

Big — O notation: Upper Bound running time
Big — Ω notation: Lower Bound running time
(No practical importance)
Big — Θ notation: Average running time

Master Theorem

--

--

--

--

Question : https://codeforces.com/problemset/problem/1337/A

Inspection:

  1. High constraints. Looping (O (n³)) is not efficient.
The next t lines describe test cases. Each test case is given as four space-separated integers a, b, c, d (1≤abcd≤10^9).

2. Rule of Triangle sides

X+Y>Z 

3. When they satisfy the rule of Triangles

Min X = a , Max X = b
Min Y = b , Max Y = c
Min(X+Y) = a+b , Max (X+Y) = b+c
if there exists z such that c<= z<=d and z< Max(X+Y)
or c<=z<=Min(d,b+c-1)
=> Triangle exists. All z in this range is a valid one.

4. If a triangle exists, find the sides .

Assume z= Min(d,b+c-1)
x,y=b,c
if z==d and d<b+c-1:
z<x+y is True
else:
z<x+y is True too

CODE

def solve(arr):
[a,b,c,d]=arr
z=min(d,b+c-1)
print(b,c,z)
t= int(input())
for _ in range(t):
arr= list(map(int, input().rstrip().split()))
solve(arr)

--

--

Question: https://leetcode.com/problems/count-primes/

INSPECTION

  1. Nothing special in this problem. Sieve of Eratosthenes implementation.

SOLUTION

import math
class Solution:
def countPrimes(self, n: int) -> int:

if n<=1:
return 0

boolean_counter=[True for j in range(n+1)]
boolean_counter[0],boolean_counter[1]=False,False
for i in range(2,int(math.sqrt(n))+1):
if (boolean_counter[i]==True and i*i<=n):
for j in range(i*i,n+1,i):
boolean_counter[j]=False
prime_count=0
for i in range(2,n):
if boolean_counter[i]:
prime_count+=1
return prime_count

--

--