Problem Link
Loop ThroughAuthor:isag2008
Difficulty
EASYProblem Statement
A group of famous artists had come together to make an album. They were provided with a single vinyl record that could only store one song. Upon finishing the album, they were unable to decide which song to store in the vinyl record. Unable to come to a conclusion, they asked the producer to choose. The group had made a total of n songs and each song had been named after a number ranging from 1 to n.
Upon checking the list arr, the producer observed that each song had been placed in an increasing order of their numbers. Starting from the top, the producer crossed off the first song and every alternate song after that till the end of the list. After this, from the remaining list, he starts off from the bottom and crosses off the last song on the list and every alternate song till he reaches the top of the list. He repeats these two steps again and again until there is one song remaining which he chooses to be the song that goes into the record. Can you help the producer find the number of the song that is stored in the vinyl record?
Solution
class Solution {
public int lastRemaining(int n) {
boolean left = true;
int remaining = n;
int step = 1;
int head = 1;
while (remaining > 1) {
if (left || remaining % 2 ==1) {
head = head + step;
}
remaining = remaining / 2;
step = step * 2;
left = !left;
}
return head;
}
}