Table of Contents
2’s complement – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
// C++
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
using namespace std;
long long c(long long A)
{
int ret = 0;
for (int i = 0; i < 32; i++) {
ret += (A & (1<<i)) > 0;
}
return (long long)ret;
}
int high(long long A)
{
int i;
for (i = 32; i >= 0; i--) {
if((A & (1LL<<i)) != 0)
return i;
}
return 0;
}
long long res(long long A)
{
assert(A >= 0LL);
if(A == 0LL) return 0LL;
// if(A > 1000000LL)
// printf("%lld: %d\n", A, high(A));
fflush(stdout);
long long h = high(A);
long long ret;
if(A == (long long)(1LL << (h + 1LL)) - 1LL)
{
ret = 2LL * res(A >> 1LL) + ((A + 1LL) >> 1LL);
} else {
long long mask = (1LL<<h);
ret = res((1LL << h)- 1LL) + res(A ^ mask) + (A - (1LL << h) + 1LL);
}
return ret;
}
long long comp2(int a)
{
long long ret = 0;
//cout << "------" << endl << a << endl;
for(int i = 0;i < 32; i++)
{
if( (a & (1 << i)) != 0)
{
// cout << "1";
ret += (1LL << i);
} else {
// cout << "0";
}
}
// cout << endl << "--------" << endl;
return ret;
}
int main()
{
int sA,sB;
long long A, B;
int N;
scanf("%d", &N);
while(N--)
{
scanf("%d%d", &sA, &sB);
A = comp2(sA);
B = comp2(sB);
long long ret;
if(A == 0) {
ret = res(B);
} else if(sB < 0) {
ret = res(B) - res(A) + c(A);
} else if(sA < 0) {
ret = res(comp2(-1)) - res(A) + c(A) + res(B);
} else {
ret = res(B) - res(A) + c(A);
}
printf("%lld\n", ret);
//cout << endl;
//cout << ret << endl;
}
return 0;
}
Java rep HackerRank Solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Solution {
private static Map<Long, Long> onesCache = new HashMap<Long, Long>();
private static long computeOnes(long n, long div) {
long onesCount = 0;
if (onesCache.containsKey(n))
return onesCache.get(n);
else if (n == 0)
return 0;
else if (n == 1)
return 1;
long a = n / div;
long b = n % div;
if (a == 1) {
onesCount += b + 1;
onesCount += computeOnes(div - 1, div >> 1);
}
onesCount += computeOnes(b, div >> 1);
onesCache.put(n, onesCount);
return onesCount;
}
private static long computeOnes(long n) {
if (n < 0)
return -n * 32 - computeOnes(-n - 1, 1<<30);
else
return computeOnes(n, 1<<30);
}
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
try {
line = br.readLine();
int tests = Integer.parseInt(line);
int[][] intervals = new int[tests][2];
for (int i=0; i < tests; i++) {
line = br.readLine();
String[] tokens = line.split(" ");
intervals[i][0] = Integer.parseInt(tokens[0]);
intervals[i][1] = Integer.parseInt(tokens[1]);
}
for (int i = 0; i < intervals.length; i++) {
int x = intervals[i][0];
int y = intervals[i][1];
if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
long n1 = computeOnes(x + (x > 0 ? -1 : 0));
long n2 = computeOnes(y + (y < 0 ? +1 : 0));
System.out.println(Math.abs(n1 - n2));
} else {
long n1 = computeOnes(x);
long n2 = computeOnes(y);
System.out.println(n1 + n2);
}
}
} catch (IOException e) {
e.printStackTrace();
} finally {
br.close();
}
}
}
Python 3 rep HackerRank Solution
#include<stdio.h>
long long num[34];
long long ONES[33];
void init()
{
int i;
ONES[0]=1;
ONES[1]=2;
num[0]=1;
for(i=1;i<33;i++)
num[i]=num[i-1]<<1;
for(i=2;i<32;i++)
ONES[i]=(ONES[i-1]<<1)+(num[i]-num[i-1])-1;
}
long long calc(int x)
{
long long sum=0,temp=0;
int i,j,k;
if(x==0)
return 0;
for(i=0;i<33;++i)
{
if(x<num[i])
break;
}
i--;
sum=ONES[i];
temp=x-num[i];
return sum+calc(temp)+temp;
}
void solve(long long a,long long b)
{
long long lo,hi,count;
if(a<0)
{
a++;
lo=calc(-a);
lo=(32*(-a))-lo;
lo+=32;
a--;
}
else
{
if(!a)
lo=calc(a);
else
lo=calc(a-1);
}
if(b<0)
{
if(b==-2)
hi=32;
else if(b==-1)
hi=0;
else
{
b+=2;
hi=calc(-b);
hi=(32*(-b))-hi;
hi+=32;
b-=2;
}
}
else
hi=calc(b);
if(a<0&&b>0)
count=hi+lo;
else
count=hi-lo;
if(count<0)count=-count;
printf("%lld\n",count);
}
int main()
{
int t,a,b;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&a,&b);
solve(a,b);
}
return 0;
}
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import os, sys
BINBITS = 8
BINSIZE = 2 ** BINBITS
INTSIZE = 32 #bits
def int2bin(x):
assert (x>=0)
return bin(x)[2:]
def ones(x):
return int2bin(x).count('1')
def compute_count(a, b):
# compute sum of number of '1's in bit representation (2's complement)
# of all numbers x such that a <= x <= b
#
n = 0
if (b < 0):
a = 2 ** INTSIZE + a
b = 2 ** INTSIZE + b
n = compute_count(b, a)
elif (a < 0): # b >= 0
a = 2**INTSIZE + a
n = compute_count(a, 2**INTSIZE -1) + compute_count(0, b)
else: # a>=0, b>=0
bina, offa = divmod(a, BINSIZE)
binb, offb = divmod(b, BINSIZE)
if binb > bina:
for i in xrange(1, binb - bina):
n += (BINBITS * (2 ** (BINBITS -1))) + \
(BINSIZE * ones((bina + i) * BINSIZE))
for i in xrange(a, (bina + 1) * BINSIZE):
n += ones(i)
for i in xrange(binb * BINSIZE, b+1):
n += ones(i)
else:
for i in xrange(a, b+1):
n += ones(i)
return n
if __name__ == '__main__':
ntests = int(sys.stdin.readline())
for i in xrange(ntests):
a, b = map(int, sys.stdin.readline().strip().split())
print compute_count(a, b)
C rep HackerRank Solution
t = int(input())
def gen(num):
if num == '':
return 0
elif num == '1':
return 1
elif num == '0':
return 0
elif num[0] == '0':
return(gen(num[1:]))
else:
return(int(num[1:],2)+1+gen(num[1:])+2**(len(num)-2)*(len(num)-1))
def func(a,b):
if a < 0 and b >= 0:
if a+b+1 == 0: return(32*(b+1))
elif a+b+1 < 0: return(32*(b+1)+func(a,-(b+2)))
else: return(32*(-a)+func(-a,b))
elif a < 0 and b < 0:
return(32*(b-a+1)-func(-b-1,-a-1))
else:
if a == 0:
return gen(bin(b)[2:])
return gen(bin(b)[2:]) - gen(bin(a-1)[2:])
for ts in range(t):
a,b = input().strip().split();a,b = int(a),int(b)
print(func(a,b))
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
