ranjani4ever
BAN USER- 1of 1 vote
AnswersLook at the following sequence:
3, 5, 6, 9, 10, 12, 17, 18, 20....
All the numbers in the series has exactly 2 bits set in their binary representation. Your task is simple, you have to find the Nth number of this sequence.
1 <= T <= 10^6
1 <= N <= 10^14
I tried to implement it as follows but it is giving me wrong answer for some hidden cases.
- ranjani4ever in United States#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define MAX 10000 #define MOD 1000000007 long long int m[MAX+1]; long long int sum; long long int binary_search(long long int n) { long long int low=0,high=MAX,mid; while(low<high) { mid=low+(high-low+1)/2; if(m[mid]<=n) low=mid; else high=mid-1; } return low; } int main() { m[0]=1; for(long long int i=1;i<=MAX;i++) m[i]=m[i-1]+i; long long int n,k,l; int t; scanf("%d",&t); for(int test=0;test<t;test++) { scanf("%lld",&n); k=binary_search(n); //cout<<m[k]<<" "; l=n-m[k]; cout<<((1<<k+1)%MOD+(1<<l)%MOD)%MOD<<"\n"; } return 0; }
| Report Duplicate | Flag | PURGE
TCS CodeVita Bit Manipulation
- 0 Answers Minheap: TLE
The following is my code for MinHeap. But it is showing TLE for some input. Can someone please help me figure out where?
- ranjani4ever July 14, 2017
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void swap(int *a,int *b){
int temp=*a;
*a=*b;
*b=temp;
return;
}
void heapify(vector<int> &heap,int index)
{
int length=heap.size();
int min=index;
int left=(index<<1)+1;
int right=(index<<1)+2;
if(left<length&&heap[left]<heap[min])
min=left;
if(right<length&&heap[right]<heap[min])
min=right;
if(min!=index)
{
swap(&heap[index],&heap[min]);
heapify(heap,min);
}
}
int main() {
int t,n;
string op;
scanf("%d",&t);
vector<int> heap;
while(t--) {
cin>>op;
//cout<<"Currently analysing"<<op<<"\n";
if(op=="insert") {
scanf("%d",&n);
heap.push_back(n);
int i=heap.size()-1;
while (i!=0&&heap[(i-1)>>1]>heap[i])
{
swap(&heap[i], &heap[(i-1)>>1]);
i =(i-1)/2;
}
}
else if(op=="getMin") {
if(heap.size()>0)
printf("%d\n",heap[0]);
else
printf("Empty\n");
/*for(int i=0;i<heap.size();i++)
cout<<heap[i]<<" ";
cout<<"\n";*/
}
else {
if(heap.size()>0)
{
heap.erase(heap.begin());
heapify(heap,0);
}
}
}
return 0;
}| Flag | PURGE