×
Home Discussions Write at Opengenus IQ
×
  • DSA Cheatsheet
  • HOME
  • Track your progress
  • Deep Learning (FREE)
  • Join our Internship 🎓
  • RANDOM
  • One Liner
Siddharth Agarwal

Siddharth Agarwal

Intern at OpenGenus | Bachelor of Technology (2017 to 2021) in Computer Science at Institute of Engineering and Technology

Lucknow, Uttar Pradesh, India •
12 posts •
Algorithms

Range Minimum query using segment tree [O(log N) update + O(log N) query]

In this article, we have solved the Range Minimum Query using Segment tree which takes O(log N) time for both update and range query. This is one of the best approaches to solve this problem.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Range Minimum query using square root decomposition [O(1) update + O(sqrt N) query]

In this article at OpenGenus, we have solved the Range Minimum Query problem using Square Root Decomposition which takes constant time O(1) for update and O(square root of N) time for range query.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Range Minimum query using Naive algorithm [O(1) update + O(N) query]

In the naive approach for range minimum query, we can execute the update query in constant time which is efficient and the best case but the query operation takes linear time O(N) which is slow depending upon number of elements and queries.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Find the number of subsets with given Bitwise OR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the Bitwise OR value of all elements in the subset. This can be solved using Dynamic Programming in polynomial time.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Find the number of subsets of an array having a given XOR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the xor value of all elements in the subset. This can be solved using Dynamic Programming in linear time.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Subset of maximum size with no pair sum divisible by 'K'

Our focus is to find the subset of largest size in which the sum of elements of a pair is not divisible by K. Using mathematical ideas, we solved it in linear time.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Find number of subsets with sum divisible by given number M

Find the number of subsets with sum divisible by given number M. We solved this using a Dynamic Programming approach with time complexity O(N * M).

Siddharth Agarwal Siddharth Agarwal
Algorithms

Find if a Subset with sum divisible by m exist

In this article, we find if a Subset with sum divisible by m exist. A naive approach takes O(2^N) time while dynamic programming takes O(N*M) time

Siddharth Agarwal Siddharth Agarwal
Data Structures

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Find the maximum sum bitonic subsequence

Given a sequence of numbers in an array A[0.......N]. Find the sum of the maximum bitonic subsequence in the array. naive algorithm will take exponential time O(N * (2^N)) but we can reduced it to O(N^2) using Dynamic programming. We will explore naive approach and go into the dynamic programming

Siddharth Agarwal Siddharth Agarwal
Data Structures

Optimizing a Segment Tree with Lazy Propagation

Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.

Siddharth Agarwal Siddharth Agarwal
Algorithms

Using Farach Colton and Bender Algorithm to solve LCA【O(V) query】

The basic idea of Farach Colton and Bender Algorithm is to traverse all the nodes using the Depth First Search graph traversal and keep a record of all the visited nodes and there corresponding heights. This allows to answer LCA queries in O(V) time complexity

Siddharth Agarwal Siddharth Agarwal
OpenGenus IQ © 2025 All rights reserved ™
Contact - Email: team@opengenus.org
Primary Address: JR Shinjuku Miraina Tower, Tokyo, Shinjuku 160-0022, JP
Office #2: Commercial Complex D4, Delhi, Delhi 110017, IN
Top Posts LinkedIn Twitter
Android App
Apply for Internship