Circular Counter


  • 0
    S

    There are people sitting in a circular fashion, print every third member while removing them, the next counter starts immediately after the member is removed. Print till all the members are exhausted.
    For example:
    Input: consider 123456789 members sitting in a circular fashion,
    Output: 369485271


  • 0
    M

    Can someone help me writing a better solution, probably constant space solution.

       static void printinCircle(String st, int k){
        	
        	char[] arr = st.toCharArray();
        	int index = 0;
        	int printCounter =0;
        	int loopCounter = 0;
        	
        	while(printCounter<st.length()){
        		if (loopCounter==k-1 && arr[index] != 'X'){
        			System.out.println(arr[index]);
            		arr[index] = 'X';
            		printCounter++;
            		loopCounter = 0;
        		}
        		if (arr[index] != 'X')
        			loopCounter++;
        		index=nextIndex(index,1,st.length());
        	}
        }
        
        
        static int nextIndex(int currentIndex, int increment, int size){
        	return currentIndex+increment < size ? currentIndex+increment : currentIndex+increment-size;
        }
    

  • 4
    P

    said in Circular Counter:

    circular fashion

    a = ['1','2','3','4','5','6','7','8','9']
    
    def josepheus(int_list, skip):
      skip = skip - 1 #list starts with 0 index
      idx = 0
      while len(int_list)>0:
        idx = (skip+idx)%len(int_list) #hashing to keep changing the index to every 3rd
        print int_list.pop(idx)
    
    
    josepheus(a,3)
    

  • 0
    P

    #hashing to keep changing the index to every 3rd

    @pg2286 can you please elaborate a bit on this one? i'm not grasping the logic behind this hashing.


  • 0
    P

    @peetonn the reason for hashing is that we have to find the index of the item which needs to be removed.
    So for e.g. if you iterate with the initial list of folks with every 3rd item eliminated:

    INPUT
    int_list = 123456789
    skip = 3

    While Iteration:

    1. int_list = 123456789
      len(int_list) = 9
      skip = 2 # as int_list starts from 0
      idx = (0 + 2) % 9 #here previous index was 0
      so 3rd element which is 3 in this case eliminated
    2. int_list = 12456789
      len(int_list) = 8
      idx = (2 + 2) % 8 #here previous index was 2
      so 3rd element starting from 4th person which is 6 would be deleted.

    and so on
    The reason why we have to do this way is I am not putting the people who escape at the back of list so ideally in 2 while iteration the list should have been
    45678912 and then no hashing needed to be done, which means you can directly remove the third element


  • 0
    J

    Here is Go implementation :

    func circularCounter(list []int, skip int) {
    skip = skip - 1 //index is 0
    idx := 0
    for len(list) > 0 {
    idx = (idx + skip) % len(list)
    fmt.Printf("%d ", list[idx])
    list = append(list[:idx], list[idx+1:]...)
    }
    return
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.