All Questions
Tagged with complexity c
11 questions
7
votes
3
answers
1k
views
Naive attempt at implementing a dictionary in C. Stack-based and O(n)
I am a C++ programmer trying to learn C.
Please critique my C code here. I am trying to make a small "hash table" that's \$O(n)\$ lookup. But, it is stack-based and so should be no slower ...
- 397
2
votes
2
answers
3k
views
Dynamic Array Based Stack in C
I wrote a dynamic stack in C that uses an array as a structure. I tried to maintain O(1) for push and pop and believe I have done so. I want to know what can be written in a cleaner way and if there ...
- 123
1
vote
1
answer
168
views
Find the maximum GCD of a number with respect to all the values in an array for competitive programming
Here is the Question. Find the largest GCD of the input variable with the values of an array.
Inputs are as follows:- First-line contains two integers, N and Q.
Second-line contains N integers which ...
2
votes
1
answer
113
views
Permutation 1...N. Answer queries "How many numbers between [X,Y] position are in the interval [L,K]"?
So I am solving this task:
We have an permutation of the numbers 1..n.
I need to answer m queries:
-How many numbers between X-th and Y-th position are in the interval [L,K] (<=k and >= L)?
So my ...
- 121
1
vote
2
answers
133
views
Unbalanced Binary Search Tree insertion and search with random and sorted values
I have created this unbalanced binary search tree in C. Can anyone say this is a true approach or not? I have two scenarios for insertion and search: in the first scenario I am inserting 10000 random ...
- 113
1
vote
2
answers
379
views
Massive file sorting algorithm
I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, ...
- 13
0
votes
1
answer
1k
views
Printing a singly linked list with time complexity O(n) and space complexity O(sqrt(n)) [closed]
My aim is to write a method which prints contents of a singly linked list in reverse order with time complexity \$O(n)\$ and space complexity \$O(\sqrt{n})\$. The best I could come up with is to store ...
- 169
-4
votes
2
answers
2k
views
"Magic Fraction" finder
A Magic Fraction for N is one that has the following properties:
It is a proper fraction (the value is < 1)
It cannot be reduced further (the GCD of the numerator and the denominator is 1)...
2
votes
2
answers
114
views
Two squares or not two squares - constant time optimization
I have been trying to solve this problem, and after a bit of googling, I realised a \$O(\sqrt{n})\$ time complexity works fine (though the algorithm suggested is different from that I have used). My ...
- 339
6
votes
2
answers
1k
views
Genomic Range Query
Recently I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of this training).
The proper approach for this question is using ...
- 63
2
votes
1
answer
2k
views
Finding the pairs of intersecting discs
I have been following this question on SO, copied below. I put together a solution, but which is \$O(n^2)\$. In order to get a more efficient \$O(n \log n)\$ or \$O(\log n)\$ solution, I tried to ...
- 297