CareerCup

Explaining the question further:-

Arr-3 is formed by eliminating 3rd, 6th, 9th ... (x*3)th from Arr-2
Now since Arr-2 was {1,3,5,7,9,11,13 ...} (after eliminating 2nd,4th,6th (x*2)th elements from Arr-1) -
Arr-3 eliminates 5(3rd element), 11(6th element) ... from Arr-2 and forms Arr-3={1,3,7,9,13,15 ...}

So Arr-k formed by removing x*kth element from Arr-(k-1) immediate preceding array of Arr-k.

Please revert if am still not clear.

public static void checkExistense(int z, int k){
		int d = checkPrime(z);
		if(d==0){
			System.out.println(z+" is present in Arr-"+k);
			return;
		}
		if(k>d){
			System.out.println(z+" is not present in Arr-"+k);
		}else{
			if(z%2==0 || z%3==0 || z%5==0){
				System.out.println(z+" is not present in Arr-"+k);
			}else{
				System.out.println(z+" is present in Arr-"+k);
			}
		}		
	}
	
	public static int checkPrime(int z){
		for(int i=(int) Math.sqrt(z);i>1;i--){
			if(z%i==0)
				return i;
		}
		return 0;
	}

public static boolean exists(int z, int k)
{
if(k<=1) return true;
if(z<1) return false;
if(z==1) return true;
if(z<=k) return false;
for(int i=2;i<=k;i++)
{
if(z%i==0)
return false;
}
return true;
}

x=z;
for(i=2; i<=k; i++)
{
if(x%i==0)
return " z exist in Arr-(k-1) ";
else
x=(x/k)*(k-1) + x%k; // used to calculate the position of z in Arr-i
}

return " z exist in Arr-k at position x";


Space Complexity: O(1)
Time Complexity: O(K)

Is this really from msft? Anyways

for(int i=2;i<=k;i++){
  if(i>z)
    return true;
  if(z%i==0)
    return false;
  z = z - z/i; // z/i returns integer part only
}

import math

def alg(z, k):
    for i in range(2, k+1):
        if z % i == 0:
            return False
        else:
            z = z - math.floor(z/i)
    return True


print(alg(9, 3))
print(alg(9, 4))

array-2 is all elements of array except multiples of 2
array-3 is all elements of array except multiples of 2, 3
array-4 is all elements of array except multiples of 2,3,4
and .... so on
array-k is all elements of array except multiples of 2,3,4,5,....k-1

For each number i from 2 to k, if z is multiple of i, a number z can not be in array.
z can be a multiple of number from 2 to k, if its multiple of prime between 2 to k
Find out prime numbers between 2 to k (O(k) time and space complexity).
Check if z is multiple of prime numbers between 2 to k (O(k) time complexity)
If it is then z can't be in array-k
If its guaranteed that z is always taken from array then we end here otherwise then run binary search(O(logn) time complexity) if array is sorted (else linear search O(n) or sort and search(O(logn)) to find z in array. if found z is in array-k, else it is not in array-k

static bool Exists(int arg, int k)
        {
            for (int mod = 2; mod <= k && mod <= arg; mod++)
            {
                if (arg % mod == 0) return false; else arg -= (arg / mod);
            }
            return true;
        }

public static boolean exists(int number,int k) {
        for(int i = 2;i <= k && i <= number;i++) {
            if(number % i == 0) {
                return false;
            } else {
                number -= (number / i);
            }
        }
        return true;
    }

Arr-k is formed by eliminating x*k elements from Arr-(k-1)，NOT Arr-1。
I dont think anyone really undertand what it means, except the author.

Say if we are to check for value N in round K, then we check from 1st round till Kth round. At each round we are interested in the index of N.
- Clearly when K=2 index of N is N itself (as nothing has been eliminated yet)
- When K=3 then index of N is N - (floor(N/2)); as floor(N/2) elements have been eliminated when K=2

Also in each round (say K) a number whose index is 'X' is eliminated if X%K=0
Therefore we start from 1st round and continue up and see if the number survives till Kth round.

bool isPresent(int N, int K) {
 int curRound=2, curIndex=N;
 while (curRound < K) {
   if (curIndex%curRound==0) return false;
   curIndex = curIndex - (floor(curIndex/curRound));
   curRound++;
 }
 return true
}

Time complexity: O(K)
Space complexity: O(1)

So for this if k = 1 then it exists always else for z to exist it should not be divisible by 2 and 2+3 and 2+3+4 and.........2+3+4+....+k.

public static void main (String[] args) throws java.lang.Exception
	{
		Scanner inp = new Scanner(System.in);
		int k = inp.nextInt();
		int z = inp.nextInt();
		if(existsnum(k,z)) 
			System.out.println("Yes it exists");
		else
			System.out.println("No it doesn't");
	}
	public static boolean existsnum(int k, int z){
		if(k==1)	return true;
		int temp = 2;
		for(int i=2;i<=k;i++){
			if(z%temp==0)	return false;
			temp+= i+1;
			
		}
		return true;
	}

You need to check only for primes in 2 to k..You can use sieve method for that.
So space O(k) time O(kloglogk)..
However, if you check for every k, space=O(1), time is O(k). I don't undderstand which one of the two is better? Is mod operation costly so that we should use the first way, or should we go with the basic intuition of the second method?

public bool ElementExists(int[] array,int z, int k)
{
int index = -1;

for (int i = 0; i < array.Length; i++)
{
if (array[i] == z) { index = i; break; }
}


if (index == 1) return true;

for (int i = 2; i <= k; i++)
{
if (index % i == 0) return false;
index = ((i-1)*(index/i))+(index%i);
}

return true;
}

public bool ElementExists(int[] array,int z, int k)
{
int index = -1;

for (int i = 0; i < array.Length; i++)
{
if (array[i] == z) { index = i; break; }
}


if (index == 1) return true;

for (int i = 2; i <= k; i++)
{
if (index % i == 0) return false;
index = ((i-1)*(index/i))+(index%i);
}

return true;
}

public class ArrayK {

    public static void main(String[] args){

        int z=5;
        int index=z;
        int k=3;
        int i;

        for(i=2;i<=k;i++){

            if(index%i !=0) {

                if(i==k){

                    System.out.print("the number with value  " + z +"   is present in Array " + k);
                }

            index = index-(index/i);

            }

            else

            {
                System.out.print("the number with value  " + z +"   is not present in Array " + k);

                break;
            }


        }




    }

public static boolean isPresentInArray_K(int number, int k)
	{
		//base conditions
		if(k == 1)
			return true;
		
		if(k >= 2 && (number % 2) == 0)
			return false;
				
		// approach for the Array3 and after
		else
		{
			int positionInArrayTwo = (int) Math.ceil((double)number/2);
			System.out.println("The position of " + number + " in Array_2 is : " + positionInArrayTwo);
			
			int positionInPreviousArray = positionInArrayTwo;
			int positionInCurrentArray;
			
			for(int i = 3 ; i <= k ; i++)
			{
				if(positionInPreviousArray % i == 0)
					return false;
				
				positionInCurrentArray = positionInPreviousArray - (positionInPreviousArray / i);
				System.out.println("The position of " + number + " in Array_" + i + " is : " + positionInCurrentArray);
				positionInPreviousArray = positionInCurrentArray;
			}
			return true;

}

1 . Z cannot be multiple of any number between [2,k].
2. Z can be any prime number <= N
3. Z can be any number which is multiple of [k+1,N].

// Test.cpp : main project file.

#include "stdafx.h"
#include <iostream>

using namespace System;

#define MAX_DEPTH_INPUT 100

bool test(int k, int z)
{
    //could use alloc to cover more than the limit
    if (k > MAX_DEPTH_INPUT) return false;
    int inc[MAX_DEPTH_INPUT] = {0};

    if (k == 0 || z <= 0) return false;
    if (k == 1 || z == 1) return true;

    //Gen the increament, 2, 4, 6, 2, 4, 6 for depth 4, etc.
    for (int i=0; i<k-1; i++)
    {        
        inc[i] = 2 * ((i % (k-1)) + 1);
    }

    //Test
    bool result = false;
    int sum = 1;
    int add = 0;

    while (sum <= z)
    {
        sum += inc[add % (k-1)];
        if (sum == z) result = true;
        add++;
    }

    return result;
}

int main(array<System::String ^> ^args)
{
    int k = 2;
    int z = 2;

    for (k=0; k<10; k++){
        for (z = 0; z<100; z++){
            printf("K: %d, Z: %d, Result: %d\n", k, z, test (k, z));
        }
    }

    return 0;
}

I don't know if I have understood the question properly......also feel should be Arr3={1,2,4,5,7,10,11,13,14,16,17,19,.....} is what understood from explaination of Arr2. If this true then

boolean isValueExistInArr=false;
if (z%k==0){
   isValueExistInArr=true;
}else{
isValueExistInArr=false;
}

#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{
int arr[50]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
int i,j;

printf("Array elements are:-");
for(i=0; i<25; i++)
printf("%5d", arr[i]);

printf("\n");

int Array_kth, No;
printf("Enter the kth Array and No to find in Kth array:-");
scanf("%d %d", &Array_kth, &No);

bool found = false;
if( Array_kth==1 )
{
printf("Found the Element in first array\n");
return 0;
}

for(i=1; i<=No; )
{
if(i==No)
{
found = true;
break;
}
for(j=1; j<Array_kth; j++)
{
if(i==No)
{
found = true;
break;
}
i=i+(j*2);
}

if(found)
break;
}

if(found)
printf("Number %d Found the Element in array %d\n", No, Array_kth);
else
printf("Number %d Not Found the Element in array %d\n", No, Array_kth);

printf("\n");

return 0;
}

System.out.println("");

public static void main(String[] args) {

		int n = 100;
		int z = 39;
		int k = 7;
		int indexToRemove = 2;
		Integer[] arr = new Integer[n];
		for (int i = 1; i <= n; i++) {
			arr[i - 1] = i;
		}
		Queue<Integer> q = new LinkedList<Integer>(Arrays.asList(arr));
		for (int i = 0; i < k - 1 && !q.isEmpty(); i++) {
			int counter = 0;
			int initialSize = q.size();
			while (counter < initialSize) {
				for (int j = 0; j < indexToRemove - 1 && counter < initialSize; j++, counter++) {
					q.offer(q.poll());
				}
				if (counter < initialSize) {
					q.poll();
					counter++;
				}
			}
			indexToRemove++;
		}

		System.out.println("Element exists: " + q.contains(z));

	}