Fibonacci Factor Problem

Story

Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. 

Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.

Input Format  

First line of the input contains an integer T, the number of testcases.

Then follows T lines, each containing an integer K.

Output Format

Output T lines, each containing the required answer for each corresponding testcase.

Sample Input 

3

3

5

161

Sample Output

3 3

5 5

21 7

Explanation 

There are three testcases. The first test case is 3, the smallest required fibonacci number  3. The second testcase is 5 and the third is 161. For 161 the smallest fibonacci numer sharing a common divisor with it is 21 and the smallest number other than 1 dividing 161 and 7 is 7.

Constraints :

1 <= T <= 5

2 <= K <= 1000,000

The required fibonacci number is guranteed to be less than 10^18.

My Answer: (I am no sure if it is correct.)

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

using namespace std;

int fb(int i);

int _tmain(int argc, _TCHAR* argv[])
{
 int count = 0;
 cin >> count;
 int *input = new int[count];
 for (int i = 0; i<count; i++)
 {
  cin >> input[i];
 }

 for (int i = 0; i<count; i++)
 {
  int k = 1;
  int fbNumber = 1;
  while (fbNumber <= input[i]) 
  {
   for (int x=2; x<=fbNumber; x++)
   {
    if (fbNumber % x == 0 && input[i] % x == 0 )
    {
     cout << input[i] << " " << fbNumber << endl;
    }
   }

   k++;
   fbNumber = fb(k);
  };
 }

 return 0;
}

int fb(int i)
{
 if (i<=1)
  return 1;

 if (i==2)
  return fb(1);

 return fb(i-1) + fb(i-2);
}

Reference:
https://amazon.interviewstreet.com/challenges/dashboard/#problem/4fd653336df28

Candies giving problem

Story

Alice is a teacher of kindergarten. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.

Input

The first line of the input is an integer N, the number of children in Alice's class. Each of the followingN lines contains an integer indicates the rating of each child.

Output

On the only line of the output print an integer describing the minimum number of candies Alice must give.

Sample Input

3
1
2
2

Sample Output

4













My Answer (I am no sure if it is correct.)

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

using namespace std;

class child {
public:
    child() : m_candy(1) {}
    child(int rating) : m_rating(rating), m_candy(1) {}

    int Rating() { return m_rating; }
    void setRating(int rate) { m_rating = rate; }
    int Candy() { return m_candy; }
    void setCandy(int candies) { m_candy = candies; }

private:
    int m_rating;
    int m_candy;
};

void showCandies(int[], int);

int _tmain(int argc, _TCHAR* argv[])
{
    const int count = 10;
    int childs_rating[] = {9,2,3,3,3,2,1,1,3,4};

    showCandies(childs_rating, count);

    cin.get();
 return 0;
}

void showCandies(int* rating, int count)
{
    child* childs = new child[count];
    for(int i=0;i<count;i++)
    {
        childs[i].setRating(rating[i]);
    }

    bool run = false;
    do
    {
        run = false;

        for(int i=0;i<count-1;i++)
        {
            if( childs[i].Rating() ; childs[i+1].Rating() && childs[i].Candy() <= childs[i+1].Candy())
            {
                run = true;
                childs[i].setCandy(childs[i+1].Candy() + 1);
            }

            if( childs[i+1].Rating() ; childs[i].Rating() && childs[i+1].Candy() <= childs[i].Candy())
            {
                run = true;
                childs[i+1].setCandy(childs[i].Candy() + 1);
            }
        }

        for(int i=0;i<count;i++)
        {
            cout << childs[i].Candy() << '\t';
        }
        cout << endl;
    } while(run);

    delete[] childs;
}

Reference:
http://stackoverflow.com/questions/11292913/candies-interviewstreet

How to sum the Integers from 1 to N.

Question:
How to sum the Integers from 1 to N.

Answer:

#include "stdafx.h"
#include 

using namespace std;

int allPlus(int n);

int _tmain(int argc, _TCHAR* argv[])
{
    const int n = 100;
    int sum = allPlus(n);

    cout << sum << endl;

    std::cin.get();
 return 0;
}

int allPlus(int n)
{
    if (n == 0)
        return 0;

    return n + allPlus(n-1);
}

Advanced Answer:
Change function allPlus below for O(1) time complexity

int allPlus(int n)
{
    return (1 + n) * n / 2;
}

* All answer just my answer, I am no sure if it is correct.

Find duplicated numbers in an array.

Question:
Given an array with N+M items, each item is number between 1 to N, please give a O(M+N) solution to print all duplicated numbers.

Answer:

#include "stdafx.h"
#include 

using namespace std;

void printDuplicate(int arr[], int nm, int n);

int _tmain(int argc, _TCHAR* argv[])
{
    const int n = 10, m = 5;
    const int nm = n+m;
    int arr[nm] = {1,2,3,4,5,6,7,8,9,10,1,2,3,4,2};

    printDuplicate(arr, nm, n);

    std::cin.get();
    return 0;
}

void printDuplicate(int arr[], int nm, int n)
{
    int* pArray = new int[n];
    for (int i=0; i<n; i++)
    {
        pArray[i] = 0;
    }

    for (int i=0; i<nm; i++)
    {
        int value = arr[i];
        pArray[value]++;

        if (pArray[value] == 2)
            cout << value << endl;
    }
}

Advanced Question:
Give an answer without using extra space.

Answer:
Change function printDumplicate as below.

void printDuplicate(int arr[], int nm, int n)
{
    int pArray = 0;

    for (int i=0; i 0)
            cout << value << endl;

        pArray |= (1 << (value-1));
    }
}

Thinking:
If you use bits of an integer variable to keep all status, remember that there are 32 bits only.


* All answer just my answer, not the best one.

How to swap two variables without using a temporary variable.

Question:
How to swap two variables without using a temporary variable.


Anser:
There are 3 methods to tackle this issue.

1. XOR

a = a ^ b;
b = a ^ b;
a = a ^ b;

2. Addition and Minus

a = a + b;
b = a - b;
a = a - b;

3. Multiplying and Division

a = a * b;
b = a / b;
a = a / b;

Thinking:
It is possible overflow if you use method 2 and 3.

Why method 1 work? Because N ^ N = 0 and N ^ 0 = N, so you can think

a' = a ^ b;
b' = a' ^ b 
   = a ^ b ^ b 
   = a ^ 0 
   = a;
a'' = a' ^ b' 
    = a ^ b ^ a 
    = 0 ^ b 
    = b;

Reference:
http://emn178.pixnet.net/blog/post/92113175
http://emn178.pixnet.net/blog/post/92389195-%E9%9D%A2%E8%A9%A6%E5%B8%B8%E8%A6%8B%E7%A8%8B%E5%BC%8F%E8%80%83%E9%A1%8C-%E7%A8%8B%E5%BC%8F%E5%AF%A6%E5%81%9A

internal and external iterator

What different between internal and external iterator?


external iterator:

It is a separate class that can step through its container/collection.

So you can control the logic to get the item what you want.

ex.

std::vector<int> v;
for(vint::iterator it=v.begin(), it!=v.end(); ++i)
    std::cout << *it << "\n";

internal iterator:

It is implemented with member functions to step through.

You only can get the items in turn, but it is more easy to use than external iterator.

ex.

MACRO_FOREACH(v)
{
    std::cout << v << "\n";
}