return the number of times is state of bulb changed?

Question

Today in an exam I faced a problem which is Toggled Switches(Hacker Earth) as it is an exam question So, I am unable to send the question or its link (exactly).

Problem: we have to print a number representing the number of times do bulb changed its state. The bulb is attached to the "n" number of switches. So the bulb will be in the "on" state only when half or more than half of the given n of switches to be "on".

1 represents on state

0 for off respectively.

There is also a query that will be given to represent which switch has to be toggled ( change from on to off or vice-versa 1 ->0 or 0->1). So, by toggling may or may not the bulb state change. so we have to return the number of times it changed its state.

input:

1 - number of test case

3 - number of switches (n)

1 1 0 - initial all n switches states

3 - number of switches to be toggled

3 2 1 -> (3 represents third switch i.e as index wise second in switches array.) switches that have to be toggled.

output:

1 - number of times the bulb changed its state .

explanation: initial array or switches state [1, 1, 0] as half or more than half switches are in on. hence bulb is in on state. as per queries [3,2,1]

we have to toggle the 3 rd switch. As initially third is in off [1,1,0] after toggling it changes to on [1,1,1] present switches state. as all are in on position bulb is on. ( no changes in the state of the bulb)

Now, have to toggle 2 nd switch so [1,1,1] changes to [1,0,1] switches states as half switches are on the bulb is on. ( no changes in the state of the bulb)

Now, 1 st switch to be toggled. Hence [1,0,1] changes to [0,0,1]. as not equal or more than half switches are in on states hence bulb is going to be off. ( now bulb state is changed)

Hence the output is one.

I wrote the answer to this I am only able to solve the sample test case. No hidden test case is got the right answer and some got time exceeds error. so totally 0 marks.

I am a beginner so please explain vividly where I am wrong what is wrong? how it can be efficient ?.

and my code is

    import java.util.*;
    public class Main{
        static Scanner scan = new Scanner(System.in);
        public static void main(String[] args) {
        int test_cases = scan.nextInt();
    while(test_cases>0){
        //number of switches
        int n  = scan.nextInt();
        // contains on / off positions of switches
        int [] switches = new int[n];
        for(int i =0;i<n;i++)
        switches[i]=scan.nextInt();
        //number of queries 
        int q = scan.nextInt();
        //  starts at 1 i.e queries[0]=1 but represents switch index 1(queries representing switch position and tha position starts from 1)
        int [] queries  = new int[q];
        for(int i =0;i<q;i++)
        queries[i]=scan.nextInt();
        int result  = toggled(n,switches,q,queries);
        System.out.println(result);
        test_cases--;
    }
    }
    static int toggled(int n,int switches[],int q,int queries[]){
        if(n==1)
        return q;
        int result =0;
        //giving switch state on or off
        boolean initial = on(switches);
        //System.out.println("initial is "+initial);
        //to represent on or off for all toggle including initial
        boolean [] states = new boolean[q+1];
        states[0] = initial;
        int count  = 0;
        //to represent index of states
        int state_count =1;
        while(count<q){
            if((switches[queries[count]-1] & 1 )== 1)
            switches[queries[count]-1] = 0;
            else
            switches[queries[count]-1] = 1;
     
     states[state_count++]=on(switches);
     count++;
        }
       //System.out.println("state_count is "+state_count);
       for(int i =1;i<state_count;i++){
           if(initial ^ states[i] )
           {
               result+=1;
               initial = states[i];
           }
       }
       return result;
    }
    //method to evaluate whether to consider on or off ( to on(bulb) have to on atleast half of the switches)
    static boolean on(int arr[]){
        int sum = 0;
        for(int i =0;i<arr.length;i++)
            sum+=arr[i];
        
        if(sum>=arr.length/2.0)
            return true;
            else 
            return false;
            
        
    }
}

Answer 1

Formatting

First off, the formatting including indentation is really terrible. For other people to be able to read and understand your code you need to abide to commonly accepted code conventions.

For example:

if(n==1)
return q;
int result =0;

On a casual read through it is impossible to tell to which line(s) the if applies to. At the very least you need to indent return q;. Better would be to always use braces.

Also use spaces between keywords and round brackets and around operators. Use blank lines to separate logical parts of code (especially between methods).

The lines above should look like:

if (n == 1) {
    return q;
}

int result = 0;

Look up some Java code conventions (for example, https://google.github.io/styleguide/javaguide.html) and use them. Your editor/IDE should also have a function to format the code for you. If it doesn't, use a different editor/IDE.

---

NB: I don't know if it is on topic or appropriate, but you have the same problem with your English text. Documentation is an important part of coding and while your text is understandable and contains all information, it appears disorganized. Inconsistent spacing, punctuation and capitalization makes it difficult to read.

---

Naming

Your variable names could be better. This can easily be seen due to your comments. Instead of the comments use those words as variable names. For example:

int numberOfSwitches = scan.nextInt(); // or maybe `switchCount`

int[] switchPositions = new int[numberOfSwitches];
for (int i = 0; i < numberOfSwitches; i++) {
    switchPositions[i] = scan.nextInt();
}

int numberOfQueries = scan.nextInt();

Also variable names should be camelCase and not snake_case.

---

Unconventional coding choices

if((switches[queries[count]-1] & 1 )== 1)
switches[queries[count]-1] = 0;
else
switches[queries[count]-1] = 1;

(First again: formatting/indentation) The ... & 1 seems unnecessary. the switches should only contain 0 or 1. You should consider using boolean for switches anyway.

Also queries[count]-1 is repeated unnecessarily. Better would be for example:

int switchIndex = querys[count] - 1;
switches[switchIndex] = 1 - switches[switchIndex];

---

The use of ^ (xor) seems unnecessarily cryptic. You could just use !==.

---

if(sum>=arr.length/2.0)
           return true;
           else 
           return false;

This kind of structure is unnecessary. The if expression is already boolean, so you can return its result directly:

return sum >= arr.length / 2.0;

Personally I would avoid float arithmetic here. I'd write it as:

return sum * 2 >= arr.length;

(This would be problematic with very large arrays, but that's an unlikely edge case.)

---

Performance

The performance problem is probably due to the use of two loops (first caculating all staes and then counting the changes). The whole calculation could be done in a single loop, because you don't need to store all the states. You only need to remember the last state. Also counting the number of switches to check if the light is on, only needs to be once at the beginning. In the loop the number of switches can be implied from the query.