Algorithm


Problem Name: 30 days of code - Day 29: Bitwise AND

Problem Link: https://www.hackerrank.com/challenges/30-bitwise-and/problem?isFullScreen=true

Objective
Welcome to the last day! Today, we're discussing bitwise operations. Check out the Tutorial tab for learning materials and an instructional video!

Task
Given set S = {1,2,3,...,N} . Find two integers, Aand B (where A < B ), from set S such that the value of A&B is the maximum possible and also less than a given integer, K . In this case,& represents the bitwise AND operator.

Function Description
Complete the bitwiseAnd function in the editor below.

 

bitwiseAnd has the following paramter(s):
- int N: the maximum integer to consider
- int K: the limit of the result, inclusive

Returns
- int: the maximum value of A&B within the limit.

Input Format

The first line contains an integer, T, the number of test cases.
Each of the T subsequent lines defines a test case as 2 space-separated integers, N and K , respectively.

Constraints

  • 1 <= T <= 103
  • 2 <= N <= 103
  • 2 <= K <= N

Sample Input

STDIN   Function
-----   --------
3       T = 3
5 2     N = 5, K = 2
8 5     N = 8, K = 5
2 2     N = 8, K = 5

Sample Output

1
4
0

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);


void calculate_the_maximum(int n, int k) {
  //Write your code here.
int i,j;
int max=0;
int h=0;
for(i = 1; i  <  n; i++)
{
  for(j=i+1; j  < = n; j++)
  {  int v = i&j;
     if(v >= k)
        break;
     if(max < v)
        max = v;
         
   }
   
}
printf("%d\n",max);


}


int main()
{
    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int t_itr = 0; t_itr  <  t; t_itr++) {
        char** nk = split_string(readline());

        char* n_endptr;
        char* n_str = nk[0];
        int n = strtol(n_str, &n_endptr, 10);

        if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

        char* k_endptr;
        char* k_str = nk[1];
        int k = strtol(k_str, &k_endptr, 10);
        calculate_the_maximum(n,k);
         if (k_endptr == k_str || *k_endptr != '\0') {
          exit(EXIT_FAILURE);
        }
    }

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length  <  alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ">;
    }

    return splits;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;

    int N, K;
    
    for(int i = 0; i  <  t; i++)
    {
        vector<int> s;
        cin >> N >> K;

        for(int j = 1; j  < = N; j++)
        {
            s.push_back(j);
        }

        int maximum = 0;

        for(int A = 0; A  <  N; A++)
        {
            for(int B = A + 1; B  <  N; B++)
            {
                if((s[A] & s[B]) < K && (s[A] & s[B]> > maximum)
                    maximum = (s[A] & s[B]);
            }
        }

        cout << maximum << endl;
    }

    return 0;
}

Copy The Code & Try With Live Editor

#3 Code Example with C# Programming

Code - C# Programming


using System;

class Solution
{
    static void Main(String[] args)
    {
        var T = int.Parse(Console.ReadLine());

        for (int i = 0; i  <  T; i++)
        {
            var input = Console.ReadLine().Split(' ');
            var N = int.Parse(input[0]);
            var K = int.Parse(input[1]);

            int max = 0;

            for (int j = 1; j  <  N; j++)
            {
                for (int k = j + 1; k  < = N; k++)
                {
                    int h = j & k;
                    if (h  <  K && max < h) max = h;
                }
            }

            Console.WriteLine(max);
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Golang Programming

Code - Golang Programming


package main

import "fmt"

func main() {
	var t, n, k, max int
	fmt.Scan(&t)

	for i := 0; i  <  t; i++ {
		fmt.Scan(&n, &k)
		for j := 1; j  < = n; j++ {
			for v := 1; v  <  j; v++ {
				andResult := j & v
				if andResult < k && andResult > max {
					max = andResult
				}
			}
		}
		fmt.Println(max)
		max = 0
	}
}
Copy The Code & Try With Live Editor

#5 Code Example with Java Programming

Code - Java Programming


import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();

        for (int i = 0; i  <  T; i++) {
            int N = in.nextInt();
            int K = in.nextInt();

            int max = 0;

            for (int j = 1; j  <  N; j++) {
                for (int k = j + 1; k  < = N; k++) {
                    int h = j & k;
                    if (h  <  K && max < h) max = h;
                }
            }

            System.out.println(max);
        }
    }
}
Copy The Code & Try With Live Editor

#6 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'bitwiseAnd' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER N
 *  2. INTEGER K
 */

function bitwiseAnd(N, K) {
    // Write your code here

}

function main() {
    var t = parseInt(readLine());
    for(var a0 = 0; a0  <  t; a0++){
        var n_temp = readLine().split(' ');
        var n = parseInt(n_temp[0]);
        var k = parseInt(n_temp[1]);
        
        var a = k - 1;
        var b = (~a) & -(~a);
        
        if ( (a | b) > n )
            console.log(a - 1);
        else
            console.log(a);
    }
}
Copy The Code & Try With Live Editor

#7 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'bitwiseAnd' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER N
#  2. INTEGER K
#

def bitwiseAnd(N, K):
    # Write your code here

    return (K-1 if ((K-1) | K) <= N else K-2)
    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        count = int(first_multiple_input[0])

        lim = int(first_multiple_input[1])

        res = bitwiseAnd(count, lim)

        fptr.write(str(res) + '\n')

    fptr.close()


Copy The Code & Try With Live Editor

#8 Code Example with PHP Programming

Code - PHP Programming


;
?>
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Day 28: RegEx, Patterns, and Intro to Databases solution in Hackerrank - Hacerrank solution C, C++, C#, GO, java, Js, Python & PHP in 30 days of code
Next
[Solved] #2 Day 2: Conditional Statements: Switch in Javascript HackerRank - HackerRank Javascript in 10 days