Hamming Distance – 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
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
typedef long long LL;
using namespace std;
const int LEN = 20;
const int BOUND = 1<<LEN;
int rev[BOUND],bit_cnt[BOUND];
int ONES;
void init(){
REP(i,LEN)ONES|=1<<i;
REP(i,BOUND){
bit_cnt[i]=bit_cnt[i>>1]+(i&1);
int tmp=i;
REP(j,LEN){
rev[i]<<=1;
rev[i]|=tmp&1;
tmp>>=1;
}
}
}
int a[50010];
char s[50010];
int tmp1[50010],tmp2[50010],tmp3[50010];
void get(int tmp[],int st,int len){
if(!len){
tmp[0]=0;
return;
}
int w=len/LEN;
int r=st%LEN;
int x=st/LEN;
int mask1=(1<<r)-1;
int mask2=(1<<LEN)-1-mask1;
REP(i,w){
tmp[i]=((a[x+i]&mask2)>>r)|((a[x+i+1]&mask1)<<(LEN-r));
}
r=len-LEN*w;
tmp[w]=0;
REP(i,r){
if((a[(st+w*LEN+i)/LEN]>>((st+w*LEN+i)%LEN))&1)
tmp[w]|=1<<i;
}
}
void put(int tmp[],int st,int len){
if(!len)return;
int w=len/LEN;
int r=st%LEN;
int x=st/LEN;
int mask1=(1<<r)-1;
int mask2=(1<<LEN)-1-mask1;
int mask3=(1<<(LEN-r))-1;
int mask4=(1<<LEN)-1-mask3;
REP(i,w){
a[x+i]&=mask1;
a[x+i]|=(tmp[i]&mask3)<<r;
a[x+i+1]&=mask2;
a[x+i+1]|=(tmp[i]&mask4)>>(LEN-r);
}
r=len-LEN*w;
int xx=(st+w*LEN)/LEN;
int yy=(st+w*LEN)%LEN;
REP(i,r){
if(((tmp[w]>>i)&1) != ((a[xx]>>yy)&1))
a[xx]^=1<<yy;
yy++;
if(yy==LEN){
xx++;
yy=0;
}
}
}
int main(){
init();
DRII(N,M);
RS(s);
int sn=LEN(s);
{
int x=0,y=0;
REP(i,sn){
if(s[i]=='b')a[x]|=1<<y;
y++;
if(y==LEN){
x++;
y=0;
}
}
}
DRI(Q);
while(Q--){
//REP(i,5)printf("%d",a[i]);
//puts("");
char c[4];
RS(c);
if(c[0]=='C'){
DRII(ll,rr);
ll--;rr--;
int st=(ll+LEN-1)/LEN,ed=(rr+1)/LEN;
RS(c);
int len=(rr-ll+LEN)/LEN;
if(c[0]=='a'){
REP(i,len)tmp1[i]=0;
}
else{
REP(i,len)tmp1[i]=ONES;
}
put(tmp1,ll,rr-ll+1);
}
else if(c[0]=='S'){
DRII(ll1,rr1);
DRII(ll2,rr2);
ll1--;rr1--;ll2--;rr2--;
get(tmp1,ll1,rr1-ll1+1);
get(tmp2,rr1+1,ll2-1-rr1);
get(tmp3,ll2,rr2-ll2+1);
// printf("[[%d%d]]\n",tmp1[0],tmp1[1]);
//printf("[[%d]]\n",tmp3[0]);
put(tmp3,ll1,rr2-ll2+1);
put(tmp2,ll1+rr2-ll2+1,ll2-1-rr1);
put(tmp1,ll1+rr2-rr1,rr1-ll1+1);
}
else if(c[0]=='R'){
DRII(ll,rr);
ll--;rr--;
int len=rr-ll+1;
get(tmp1,ll,len);
//REP(i,5)printf("[%d]",tmp1[i]);
if(len%LEN==0){
int w=len/LEN;
REP(i,w)tmp2[i]=rev[tmp1[w-i-1]];
}
else{
int w=len/LEN;
int r=len%LEN;
int mask1=(1<<r)-1;
int mask2=(1<<LEN)-1-mask1;
REP(i,w)tmp2[i]=rev[((tmp1[w-i]&mask1)<<(LEN-r))|((tmp1[w-i-1]&mask2)>>r)];
tmp2[w]=0;
REP(i,r)
if((tmp1[0]>>(r-i-1))&1)tmp2[w]|=1<<i;
}
put(tmp2,ll,len);
}
else if(c[0]=='W'){
DRII(ll,rr);
ll--;
int x=ll/LEN;
int y=ll%LEN;
REPP(i,ll,rr){
int now=(a[x]>>y)&1;
if(now)putchar('b');
else putchar('a');
y++;
if(y==LEN){
x++;
y=0;
}
}
puts("");
}
else if(c[0]=='H'){
DRIII(st1,st2,len);
st1--;st2--;
get(tmp1,st1,len);
get(tmp2,st2,len);
len=(len+LEN-1)/LEN;
int an=0;
REP(i,len)an+=bit_cnt[tmp1[i]^tmp2[i]];
printf("%d\n",an);
}
}
return 0;
}
Java rep HackerRank Solution
import java.io.BufferedOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
static int n;
static final int maxn = 50010 / 32 + 5;
static int []LUT = new int[(1 << 16) + 100];
static long []REV = new long[(1 << 16) + 100];
static int bits(long x) {
return LUT[(int) (x&((1 << 16) - 1)& 0xffffffffl)] + LUT[(int) ((x >> 16)& 0xffffffffl)];
}
static long getrev(long x) {
return (REV[(int) (x&((1 << 16) - 1))] << 16) | REV[(int) (x >> 16)]& 0xffffffffl;
}
public static void main(String [] args)
{
PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
Scanner sc = new Scanner(new InputStreamReader(System.in));
//StringBuffer output = new StringBuffer();
for(int i = 0; i < 1 << 16; ++i)
LUT[i] = LUT[i >> 1] + (i & 1);
for(int i = 0; i < 1 << 16; ++i) {
int res = 0;
int x = i;
for(int iter = 0; iter < 16; ++iter){
res = (res << 1) | (x & 1);
x >>= 1;
}
REV[i] = res;
}
n= sc.nextInt();
char[] s = sc.next().toCharArray();
int m= sc.nextInt();
BSet cur=new BSet();
cur.clear();
for(int i = 0; i < n; ++i)
if (s[i] == 'b')
cur.flip(i);
for(int iter = 0; iter < m; ++iter){
char c = 0;
while (c != 'C' && c != 'S' && c != 'R' && c != 'W' && c != 'H')
c = sc.next().toCharArray()[0];
int l=sc.nextInt()-1;
int r=sc.nextInt()-1;
if (c == 'C') {
char ch = 0;
while (ch != 'a' && ch != 'b')
ch = sc.next().toCharArray()[0];
int val = ch == 'b'? 1: 0;
cur.fill(l, r, val);
}
else if (c == 'W') {
StringBuilder ans = new StringBuilder();
for (int i = l; i <= r; ++i){
ans.append((char)('a'+cur.getval(i)));
}
out.println(ans);
//output.append(ans).append("\n");
}
else if (c == 'H') {
int l1 = l;
int l2 = r;
int len=sc.nextInt();
BSet tmp = cur.xor(cur.shift(l1 - l2));
int ans = 0;
r = l1 + len - 1;
for (int i = l; i <= r;) {
if (((i & 31)!=0) || (i + 31 > r)){
ans += tmp.getval(i);
++i;
}
else {
ans += bits(tmp.a[i >> 5]);
i += 32;
}
}
out.println(ans);
//output.append(ans).append("\n");
}
else if (c == 'S') {
int l1 = l;
int r1 = r;
int l2=sc.nextInt()-1;
int r2=sc.nextInt()-1;
BSet tmp = new BSet();
System.arraycopy(cur.a, 0, tmp.a, 0, cur.a.length);
cur.fill(l1, r2, 0);
cur.copy(tmp, l1, r1, r2 - (r1 - l1));
cur.copy(tmp, l2, r2, l1);
cur.copy(tmp, r1 + 1, l2 - 1, l1 + (r2 - l2) + 1);
}
else if (c == 'R') {
cur.reverse(l, r);
}
}
//out.println(output.toString());
sc.close();
out.close();
}
static class BSet {
long []a=new long[maxn];
public BSet(){
}
BSet xor(BSet o) {
BSet res=new BSet();
for(int i = 0; i < maxn; ++i)
res.a[i] = (a[i] ^ o.a[i])& 0xffffffffl;
return res;
}
BSet and(BSet o) {
BSet res=new BSet();
for(int i = 0; i < maxn; ++i)
res.a[i] = a[i] & o.a[i]& 0xffffffffl;
return res;
}
BSet or(BSet o) {
BSet res=new BSet();
for(int i = 0; i < maxn; ++i)
res.a[i] = a[i] | o.a[i]& 0xffffffffl;
return res;
}
void setint(int pos, long v) {
long val = v & 0xffffffffl;
int ind = pos >> 5;
if (ind >= 0 && ind < maxn){
a[ind] |= (val << (pos & 31))& 0xffffffffl;
}
pos += 31;
ind = pos >> 5;
if (ind >= 0 && ind < maxn){
a[ind] |= (val >> (31 - (pos & 31)))& 0xffffffffl;
}
}
void flip(int pos) {
long flip=(1l << (pos & 31));
int d =(pos >> 5);
a[d]=(a[d] ^ flip )& 0xffffffffl;
}
long getval(int pos) {
long val1= a[pos >> 5] ;
return (val1 >> (pos & 31)) & 1;
}
void setval(int pos, long val) {
if (getval(pos) != val){
flip(pos);
}
}
BSet shift(int sh) {
BSet res=new BSet();
res.clear();
for(int i = 0; i < maxn; ++i){
int pos = (i << 5) + sh;
res.setint(pos, a[i]);
}
return res;
}
void clear() {
Arrays.fill(a, 0);
}
void fill(int l, int r, int val) {
for (int i = l; i <= r;) {
if ((i & 31)!=0 || (i + 31 > r)){
setval(i, val);
++i;
}
else {
if (val!=0)
a[i >> 5] = 0xffffffffl;
else
a[i >> 5] = 0l;
i += 32;
}
}
}
void copy( BSet o, int l, int r, int to) {
int sh = to - l;
for (int i = l; i <= r;) {
if ((i & 31)!=0 || (i + 31 > r)) {
if (i + sh >= 0 && ((i + sh) >> 5) < maxn) {
setval(i + sh, o.getval(i));
}
++i;
}
else {
if (i + sh >= 0 && ((i + sh) >> 5) < maxn)
setint(i + sh, o.a[i >> 5]);
i += 32;
}
}
}
void reverse(int l, int r) {
BSet tmp = new BSet();
System.arraycopy(this.a, 0, tmp.a, 0, this.a.length);
fill(l, r, 0);
for (int i = l; i <= r;) {
if ((i & 31)>0 || (i + 31 > r)) {
int toi = r - (i - l);
setval(toi, tmp.getval(i));
++i;
}
else {
setint(r - (i + 31 - l), getrev(tmp.a[i >> 5]));
i += 32;
}
}
}
}
}
Python 3 rep HackerRank Solution
import sys
def CountBits(n):
n = (n & 0x55555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555) + ((n & 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA) >> 1)
n = (n & 0x33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333) + ((n & 0xCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC) >> 2)
n = (n & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0) >> 4)
n = (n & 0x00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00) >> 8)
n = (n & 0x0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000) >> 16)
n = (n & 0x00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000) >> 32)
n = (n & 0x0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF) + ((n & 0xFFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000) >> 64)
n = (n & 0x00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) + ((n & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000) >> 128)
n = (n & 0x0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) + ((n & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000) >> 256)
n = (n & 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) + ((n & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000) >> 512)
n = (n & 0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) + ((n & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000) >> 1024)
return n
n = int(input().strip())
s = input().strip()
c = int(input().strip())
n = len(s)
mask = int('1' * n, 2)
val = int(s.translate(bytearray.maketrans(b'ab', b'01')), 2)
outbuf = []
for i in range(c):
cmd = input().strip().split(' ')
if cmd[0] == 'C':
[l,r] = [int(x) for x in cmd[1:3]]
m = mask >> (l - 1)
m2 = m >> (r - (l - 1))
m = m ^ m2
if cmd[3] == 'a':
val &= ~m
else:
val |= m
elif cmd[0] == 'S':
[l1,r1,l2,r2] = [int(x) for x in cmd[1:]]
lead = val >> (n - l1 + 1) << (n - l1 + 1)
trail = val & (mask >> r2)
# 10 0000 0001
# 00 0000 1111
part2 = val >> (n - r2)
mid = part2 >> (r2 - l2 + 1)
part1 = mid >> (l2 - r1 - 1)
part1 &= (mask >> (n - (r1 - l1 + 1)))
mid &= (mask >> (n - (l2 - r1 - 1)))
part2 &= (mask >> (n - (r2 - l2 + 1)))
val = lead | trail;
i = l1
val |= (part2 << (n - i - (r2 - l2)))
i += (r2 - l2 + 1)
val |= (mid << (n - i - (l2 - r1 - 2)))
i += (l2 - r1 - 1)
val |= (part1 << (n - i - (r1 - l1)))
# s = s[:l1] + s[l2:r2+1] + s[r1+1:l2] + s[l1:r1+1] + s[r2+1:]
elif cmd[0] == 'R':
[l,r] = [int(x) for x in cmd[1:]]
m = mask >> (l - 1)
m2 = m >> (r - (l - 1))
m = m ^ m2
v = (val & m) >> (n - r)
v = bin(v)[2:] # strip the '0b' prefix
v = '0' * ((r - l + 1) - len(v)) + v
v = int(v[::-1], 2)
v <<= (n - r)
val = (val & ~m) | v
elif cmd[0] == 'W':
[l,r] = [int(x) for x in cmd[1:]]
# rep = s[l:r+1].replace('0', 'a').replace('1', 'b')
# rep = s[l:r+1].translate(bytearray.maketrans(b'01', b'ab'))
dump = val >> (n - r)
dump &= (mask >> (n - (r - l + 1)))
dump = bin(dump)[2:]
outbuf.append('a' * (r - l + 1 - len(dump)) + dump.translate(bytearray.maketrans(b'01', b'ab')))
elif cmd[0] == 'H':
[l1,l2,e] = [int(x) for x in cmd[1:]]
# optimization
if l1 == l2 or e < 0:
outbuf.append('0')
else:
r = max(l1,l2)
l = min(l1,l2)
x = val >> (n - (r+e-1))
y = x >> (r - l)
h = x^y
h &= (mask >> (n - e))
c = 0
while h > 0:
c += CountBits(h)
h >>= 2048
# b = bin(h)
# c = b.count("1")
# c = numberOfSetBits(h)
outbuf.append(str(c))
print('\n'.join(outbuf))
Python 2 rep HackerRank Solution
C rep HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void HandleC(char *S, int N) {
int l, r, ch;
scanf ("%d %d %c\n", &l, &r, (char *)&ch);
l--;
r--;
while (l <= r) {
S[l] = ch;
l++;
}
}
char tS[500001];
void HandleS(char *S, int N) {
int l1, l2, r1, r2, len1, len2, end=0;
int i, l, r;
scanf ("%d %d %d %d\n", &l1, &r1, &l2, &r2);
l1--;
l2--;
r1--;
r2--;
int indices[4][2] = {
{l2, r2+1}, {r1+1,l2}, {l1, r1+1}, {r2+1, N+1}
};
strncpy(tS+l1, S+l1, N-l1);
end = l1;
for (int i = 0; i < 4; i++){
int l = indices[i][0], r = indices[i][1];
if (l < r) {
strncpy(S+end, tS+l, r-l+1);
}
end += r - l;
}
/*
len1 = r1 - l1 + 1;
len2 = r2 - l2 + 1;
memcpy(tS, &S[l1], l2-l1);
memcpy(&S[l1], &S[l2], len2);
memcpy(&S[l1+len2], &tS[len1-1], (l2-l1)-len1);
memcpy(&S[l1+len2+l2-l1-len1], tS, len1);
*/
}
void HandleR(char *S, int N) {
int l, r, temp;
scanf ("%d %d\n", &l, &r);
l--;
r--;
while (l <= r) {
temp = S[l];
S[l] = S[r];
S[r] = temp;
l++;
r--;
}
}
void HandleW(char *S, int N) {
int l, r;
scanf ("%d %d\n", &l, &r);
l--;
r--;
while (l <= r) {
printf ("%c", S[l]);
l++;
}
printf ("\n");
}
void HandleH(char *S, int N) {
int l1, l2, len, hd = 0;
scanf ("%d %d %d\n", &l1, &l2, &len);
l1--;l2--;
while (len) {
if (S[l1] != S[l2])
hd++;
len--;
l1++;
l2++;
}
printf ("%d\n", hd);
}
int main() {
int N, M;
int ch;
char S[50001];
scanf ("%d\n%s\n%d\n", &N, S, &M);
while (M) {
scanf("%c ", (char *)&ch);
switch (ch) {
case 'C':
HandleC(S, N);
break;
case 'S':
HandleS(S, N);
break;
case 'R':
HandleR(S, N);
break;
case 'W':
HandleW(S, N);
break;
case 'H':
HandleH(S, N);
break;
default:
break;
}
M--;
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
