prithwiraj15's blog

Scaler CodeX 2.0
By prithwiraj15, history, 3 years ago, In English

This question appeared on Scaler CodeX 2.0 dated 06-02-22.

Statement

You are given 'N', the size of array where each element in array is Ai = i for each (1 <= i <= N). We have to exactly 'N-1' operations on this array. In each operation, we delete the last element in the array and move the second last element to the front of the array. After completion of all operations, find the remaining number in the array.

Constraints

1 <= N <= 1e9

Sample Test Case — 1

Input -> N = 5

Output -> 4

Explanation

  • Initial Array -> [1, 2, 3, 4, 5]

  • Operation 1 -> [4, 1, 2, 3] (Delete 5, then array is [1, 2, 3, 4] and move 4 to front of array getting [4, 1, 2, 3])

  • Operation 2 -> [2, 4, 1] (Delete 3, then array is [4, 1, 2] and move 2 to front of array getting [2, 4, 1])

  • Operation 3 -> [4, 2]

  • Operation 4 -> [4]

Sample Test Case — 2

Input -> N = 6

Output -> 3

Explanation

  • Initial Array -> [1, 2, 3, 4, 5, 6]

  • Operation 1 -> [5, 1, 2, 3, 4] (Delete 6, then array is [1, 2, 3, 4, 5] and move 5 to front of array getting [5, 1, 2, 3, 4])

  • Operation 2 -> [3, 5, 1, 2] (Delete 4, then array is [5, 1, 2, 3] and move 3 to front of array getting [3, 5, 1, 2])

  • Operation 3 -> [1, 3, 5]

  • Operation 4 -> [3, 1]

  • Operation 5 -> [3]

Can anyone solve this problem ???

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Simulate the game to find pattern: F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 1 F(5) = 4 F(6) = 3 F(7) = 2 F(8) = 1 F(9) = 8 F(10) = 7 F(11) = 6 . . . F(15) = 2 F(16) = 1 Clearly, F(X) = (1 << ceil(log2(X))) — X + 1.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice observation but how were you able to come up with this formula. The formula is a bit complex to acquire just by observations only, at least for me. But thank you for your help.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It's a special case of Josephus Problem (k = 2), you can read more about it on internet.

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

was problem 6 incorrect?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You could binary search on X. (If you are taking about the Burger problem)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there is a pattern try dry running for n=9 to n=16 you will get the pattern.If you are lazy to do that than i am leaving the main logic here but i would recommend dry running to get intution yourself.

ans=(smallest power of two greater than n)-n+1

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

what was the condition for the binary search I did it but it was giving WA on samples and do we have to iterate over the given array in the same order as given or in any order, can we use elements for increasing the speed multiple times? The problem statement was very unclear.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    1)Sort the given array according to burgers count (that is p).

    2)Do, binary search for the start value x, and check if you can eat all the burgers within the given time or not.

    3)Update the rate of speed (x) when your current burger count reaches to p present in the sorted array. Then x become x + q.

    4) If the remaining burger count becomes 0 then check if time taken is less than equal to C then return true, else return false;

    Note — Take time taken in double.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      but it wasn't mentioned that we can use given operations in any order I did the same thing as you described by taking the time in doubles but I didn't sort the array. it should be mentioned that you can do operations in any order. I was just sitting like an idiot in the last 1 hour and trying to solve the issue of why their answer on samples is wrong.

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I have not participated in this contest. But you can code it recursively which works in O(logN). First, observe that alternate positioned elements are deleted, now I will solve for even and odd cases separately.

Even Case:
Observe that after deleting the elements at alternate positions, we are left with a subproblem having n/2 numbers, if we know the answer of n/2 (say it is x), then the only task remaining is to find the original index of x when n numbers are there. It's easy to calculate/observe that it will 2*x-1.

Odd Case:
We will proceed in the similar way mentioned above, the only difference is that the last element will be at 1st position after one cycle of deletion. So instead of doing 2*x-1, the original index will be n-1 (for x=1) and 2*(x-1)-1 (for x>1).

Recursion:
ans(n) = 2*ans(n/2)-1 [For n = even]
ans(n) = 2*ans(n/2)-3 [For n = odd and ans(n/2)>1]
ans(n) = n-1 [For n = odd and ans(n/2)=1]

Correct me, if anything is wrong :)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

puzzle-100-people-in-a-circle-with-gun-puzzle This is a puzzle. Almost same as this one.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is my recursive solution!

#include <bits/stdc++.h>
using namespace std;

int f(int x) {
    if(x == 1) return 0;

    if(x & 1) {
        return (2*f((x + 1)/2) + 1) % x;
    }
    else {
        return 2*f(x/2);
    }
}

int ans(int x) {
    return f(x) + 1;
}

int main() {
    for(int i = 1; i < 10; ++i) {
        int result = ans(i);
        cout << i << ":\t" << result << endl;
    }
    return 0;
}

PS: Lemme know, if there is any error :)

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If you have some time, do watch this video by numberphile : https://www.youtube.com/watch?v=uCsD3ZGzMgE

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Just find the greatest power of 2 greater than or equal to N. If N equals to a power of 2 then the answer will be one, else the answer will be the next greatest power-N+1. For eg. if N=9, greatest power of 2 equals 16. The answer here will be 16-9+1 = 8.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    What is your intuition behind this approach ?? Was it plain observation ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yeah, just observation. I made more testcases and this came up to me.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Link

→ Reply
»
3 years ago, # |
← Rev. 9   Vote: I like it +1 Vote: I do not like it

I wasn't able to submit the solution on time but here's the idea I came up with I won't go into too much details. There we be at max log(n) operations so at each operation you just have to determine what is the maximum greatest number that is alive and also at each number the difference between two adjacent numbers will increase by power of two. And also look out for the case when length of the numbers alive is even and odd. 

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << setprecision(15) << fixed;

    int tc=1;
    cin>>tc;
    while ( tc-- ) {
        int n;
        cin>>n;

        int curr = n;
        int len = n;
        int cnt = 0;
        int tmp = 0;
        while( len > 1 ){
            if( len % 2 ){
                ++tmp;
                len /= 2;
                ++len;
            }
            else{
                curr -= ( 1<<cnt );
                cnt += tmp + 1;
                tmp = 0;
                len /= 2;
            }
        }

        cout<<curr<<endl;
    }
    return 0;
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain your approach a bit more ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      It's a bit of case work. Consider the sequence of odd length and even length the only difference in these sequence is that in odd sequence I'm considering the last element's contribution in the next step also.

      Consider sequence upto 5 then after one operation numbers alive will be 2,4 but 4 will not die in next step because the last element that was killed was 1 so 4 will run back and 2 will get killed in the next step. This is what I mean by the contribution of last element when length is odd. That is why I did (++len) to consider the contribution of last element when length is odd.

      And also in this case the greatest element alive will be same as previous step except the very first step. Consdier the previous case of 5 when 2, 4, 1 ( although 1 will die in first step but it doesn't matter so consdier it in the next step ). Now again the length is odd so greatest element alive in next step will be 4 and you can see that yourself.

      And the difference between adjacent numbers alive will increase by a power of two but the greatest element alive will be the same as previous ( don't consider 1 and 4, I just took 1 because it will help 4 although it will be dead in the previous step )

      But in case of even we don't have do this we don't have to do this in this the greatest element alive will change at each step take the case when there are 8 elements and see yourself. Variable curr just maintains the current greatest alive element.

      It's a bit complicated took me while to figure out as well.

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Have anyone solved question 1? I found some mistakes in the sample test cases, in the first sample test case, for the node with number 2, the answer was given 5 but actually it was coming out to be 4 according to me.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, but still my code got AC.I think while checking our code, they have corrected it.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Number of tasks solved —

[1].

[2].

[3].

[4].

[5].

[6].

Solved — task1 , task2 , task3 , task4 , task5 , task6

→ Reply