Algorithm
Problem Name: 30 days of code -
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
0Code 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;
}
#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;
}
#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);
}
}
}
#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
}
}
#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);
}
}
}
#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);
}
}
#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()
#8 Code Example with PHP Programming
Code -
PHP Programming
;
?>