Problem
This was the problem from “30 Days of Code” on Hackerrank:
Given set S={1,2,3,…,N}, find two integers A and 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.
The first line contains an integer, T , the number of test cases.
Each of the subsequent T lines defines a test case as 2 space-separated integers, N and K , respectively.
I created the program which I know is not refined but passed every test case. I want to know that does my code comes under bad programming practices.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int T = in.nextInt();
int k[] = new int [T];
int n[] = new int [T];
for(int i= 0;i<T;i++){
n[i] = in.nextInt();
k[i]=in.nextInt();
}
for(int karr =0 , narr=0;karr<k.length&& narr<n.length;karr++,narr++){
int a[] = new int [n[narr]];
int max =0;
for (int i=0;i<n[narr];i++){
a[i]= i+1;
}
for(int i=0;i<a.length;i++){
for(int j=1;j<a.length;j++){
if(a[i]<a[j]){
int andvalue = a[i]&a[j];
int temp = max ;
if( andvalue<k[karr] ){
if(andvalue>temp){
max = andvalue;
}}
}
}
}
System.out.println(max);
}
}
}
Solution
I think your code is difficult to read/understand because of:
-
Inexpressive or confusing naming
-
Lack of any documentation
-
Confusing indentation and spacing. Consider using an online code beautifier
Let’s start from the top.
int T = in.nextInt();
int k[] = new int [T];
int n[] = new int [T];
for(int i= 0;i<T;i++){
n[i] = in.nextInt();
k[i]=in.nextInt();
}
Mathematical notation doesn’t necessarily translate very well to code, where mathematical notation is meant to represent complex concepts in short form, code is meant to be concrete applications of concepts in a way that computers can process, and humans can hopefully understand.
I did a bit of renaming to make these clearer. Note that using underscore_case is not typical for Java naming, but I think casesN or nCases didn’t read well at all.
int numCases = in.nextInt();
int[] cases_N = new int[numCases];
int[] cases_K = new int[numCases];
// Populate the cases from STDIN
for (int i = 0; i < numCases; i++) {
cases_N[i] = in.nextInt();
cases_K[i] = in.nextInt();
}
This for loop’s iterator naming is misleading:
for(int karr =0 , narr=0;karr<k.length&& narr<n.length;karr++,narr++)
In reality, karr and narr are not arrays, so let’s not call them arr. Furthermore, since they are always only ever incremented together, and you already know you’ll have exactly the same number of K and N cases, there’s really no point in having both.
Also, you already have a value T (or numCases) so there is no need to get the length of the arrays.
for (int caseNum = 0; caseNum < numCases; caseNum++)
I also replaced each other occurrence of those two variables with caseNum.
This kind of reference is used a lot inside that big loop: cases_N[caseNum] and cases_K[caseNum]. Now would be a good time to just declare N and K with those values.
This makes the next section make more sense:
int N = cases_N[caseNum];
int K = cases_K[caseNum];
int a[] = new int[N];
for (int i = 0; i < N; i++) {
a[i] = i + 1;
}
Now we can give this a array a meaningful name: intsUpToN
int[] intsUpToN = new int[N];
for (int i = 0; i < N; i++) {
intsUpToN[i] = i + 1;
}
We can also replace the two instances of intsUpToN.length, since that value is already known (it’s the current N value) and we are not adding or removing anything from the array.
The code is already much easier to understand now. I added little snippets of code comments to make it more clear. I also combined the last two if checks into one with &&.
I removed temp because it is assigned the value of max and never used for anything except comparison, so we can just use max in the comparison instead.
Note that I did not address the algorithm, as algorithms are not my forte. It is clearly a brute force algorithm, and chances are someone who is good with mathematics can suggest a more efficient algorithm.
The resulting code passes all tests cases.
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int numCases = in.nextInt();
int[] cases_N = new int[numCases];
int[] cases_K = new int[numCases];
// Populate the cases from STDIN
for (int i = 0; i < numCases; i++) {
cases_N[i] = in.nextInt();
cases_K[i] = in.nextInt();
}
// Outer loop for each case
for (int caseNum = 0; caseNum < numCases; caseNum++) {
int N = cases_N[caseNum];
int K = cases_K[caseNum];
// Fill in array integers from 1 to N
int[] intsUpToN = new int[N];
for (int i = 0; i < N; i++) {
intsUpToN[i] = i + 1;
}
// Brute force method to logically "AND" all possible values,
// returning with the maximum "AND" result at the end
int max = 0;
int andValue = 0;
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (intsUpToN[i] < intsUpToN[j]) {
// This is the logical "AND" calculation
andValue = intsUpToN[i] & intsUpToN[j];
if (andValue < K && andValue > max) {
max = andValue;
}
}
}
}
System.out.println(max);
}
}
}
Adding up to @Phrancis answer. intsUpToN is not needed and is only wasting memory. intsUpToN[i] can be replaced by i + 1 and intsUpToN[j] can be replaced by j + 1.
temp is not needed and can be replaced by max
Consider to move the code to a method, to separate concerns.
I believe the method declaration would be the following:
public int maxResult(int setLength, int maxLimit)