ຊອກຫາຖານສອງຕົວເລກທີ່ນ້ອຍທີ່ສຸດໃນບັນດາຕົວເລກທີ່ທ່ານໃຫ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ສີ່ພັນ LinkedIn Microsoft Snapdeal
ການຄົ້ນຫາ ທຳ ອິດ ເສັ້ນສະແດງ

ຖະແຫຼງການບັນຫາ

ບັນຫາ "ຊອກຫາຕົວເລກຖານສອງທີ່ນ້ອຍທີ່ສຸດຂອງຕົວເລກທີ່ລະບຸໄວ້" ລະບຸວ່າທ່ານໄດ້ຮັບເລກທົດສະນິຍົມ N. ດັ່ງນັ້ນ, ທ່ານຕ້ອງຊອກຫາຕົວເລກ N ທີ່ນ້ອຍທີ່ສຸດເຊິ່ງປະກອບດ້ວຍພຽງແຕ່ສອງຕົວເລກຖານສອງ '0' ແລະ '1' ເທົ່ານັ້ນ.

ຍົກຕົວຢ່າງ

37
111

ຄຳ ອະທິບາຍລະອຽດສາມາດເບິ່ງໄດ້ຂ້າງລຸ່ມນີ້ໃນຮູບທີ່ຝັງຢູ່.

ວິທີການ

ວິທີການແມ່ນການປະຕິບັດກ BFS traversal ໂດຍໃຊ້ຊ່ອຍແນ່: '1' ເປັນຂໍ້ຂອງຮາກ. ພວກເຮົາຕື່ມຂໍ້ມູນໃສ່ '0' ແລະ '1' ໃສ່ຂໍ້ນີ້ແລະຍູ້ສາຍທີ່ໄດ້ '10' ແລະ '11' ເປັນຜົນມາຈາກ ຄິວ. ທຸກໆຄັ້ງທີ່ດຶງເຊືອກຈາກແຖວ, ພວກເຮົາໃສ່ '0' ແລະ '1' ໃສ່ສາຍທີ່ຖືກລອກແລ້ວດຶງສາຍເຊືອກທີ່ມີຜົນອອກມາໃຫ້ກັບແຖວ. ໃນລະຫວ່າງການຜ່ານຜ່າ. ຖ້າພວກເຮົາຊອກຫາເຊືອກທີ່ແບ່ງປັນຕົວເລກການປ້ອນຂໍ້ມູນໃຫ້ຄົບຖ້ວນ, ພວກເຮົາພຽງແຕ່ສົ່ງຄືນສາຍນີ້.

  1. ການຫຼຸດຜ່ອນຄວາມສັບສົນ: ພວກເຮົາຫຼຸດຜ່ອນຄວາມສັບສົນຂອງວິທີການຂອງພວກເຮົາໂດຍການຫຼຸດຜ່ອນ ຈຳ ນວນ strings ການປຸງແຕ່ງໃນໄລຍະ traversal BFS. ສຳ ລັບທຸກໆສາຍທີ່ປະມວນຜົນພວກເຮົາເພີ່ມມັນ ມູນຄ່າ mod (ສ່ວນທີ່ເຫຼືອໃນເວລາທີ່ສະຕິງທີ່ຖືກປຸງແຕ່ງຖືກແບ່ງອອກໂດຍ ໝາຍ ເລກປ້ອນຂໍ້ມູນເຂົ້າ) ເປັນກ ທີ່ກໍານົດໄວ້ hash. ຖ້າ ສຳ ລັບສາຍສະເພາະໃດ ໜຶ່ງ, ຄ່າ mod ນີ້ມີຢູ່ໃນຊຸດແລ້ວ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາບໍ່ເພີ່ມສາຍເຂົ້າໃນແຖວ BFS.
  2. ເຫດຜົນ: ເພື່ອຫຼຸດຜ່ອນຄວາມສັບສົນພວກເຮົາຫລີກລ້ຽງການເພີ່ມສາຍເຊືອກດຽວກັນ ມູນຄ່າ mod ເຂົ້າໄປໃນແຖວ. ນັ້ນແມ່ນຖ້າວ່າສາຍທີ່ມີຄ່າ mod ໂດຍສະເພາະມີຢູ່ໃນແຖວຫລືໄດ້ຖືກປະມວນຜົນແລ້ວ. ຫຼັງຈາກນັ້ນກໍ່ມີສາຍຕໍ່ໆໄປອີກພ້ອມກັນ ມູນຄ່າ mod ບໍ່ໄດ້ຖືກເພີ່ມເຂົ້າແຖວ. ເຫດຜົນ ສຳ ລັບສິ່ງນີ້: ສົມມຸດສອງເຊືອກ X ແລະ Y ທີ່ມີຄ່າ mod ດຽວກັນ (ສ່ວນທີ່ເຫຼືອເມື່ອສາຍທີ່ປະມວນຜົນຖືກແບ່ງອອກໂດຍ ຈຳ ນວນວັດສະດຸປ້ອນເຂົ້າ), X ຈະນ້ອຍກວ່າມູນຄ່າກ່ວາ Y. ໃຫ້ Z ເປັນອີກສາຍ ໜຶ່ງ ເຊິ່ງເມື່ອອຸທິດໃສ່ Y ໃຫ້ພວກເຮົາ ໝາຍ ເລກທີ່ສາມາດແບ່ງອອກໄດ້ໂດຍເລກປ້ອນຂໍ້ມູນ N. ຖ້າເປັນດັ່ງນັ້ນ, ພວກເຮົາຍັງສາມາດຕື່ມສາຍອັກສອນນີ້ໃສ່ X, ແລະຍັງສາມາດແບ່ງປັນຕົວເລກໂດຍຕົວເລກປ້ອນເຂົ້າ N. ດັ່ງນັ້ນພວກເຮົາສາມາດຫລີກລ້ຽງການເພີ່ມ Y ເຂົ້າແຖວ BFS.

ລະບົບວິເຄາະ

  1. ສ້າງແຖວ ສຳ ລັບ BFS traversal.
  2. ສ້າງເປັນ ທີ່ກໍານົດໄວ້ hash ເພື່ອກວດກາເບິ່ງວ່າສາຍທີ່ມີຄ່າ mod ສະເພາະໄດ້ຖືກພົບຫຼືບໍ່.
  3. ເລີ່ມຕົ້ນການຫລອກລວງຂອງ BFS ຫຼັງຈາກທີ່ກົດປຸ່ມ '1' ເຂົ້າໄປໃນແຖວ.
  4. ໃນຊ່ວງເວລາ Traversal:
    1. Pop ຊ່ອຍແນ່ຈາກແຖວ.
    2. ກວດເບິ່ງວ່າມັນມີຄ່າ modular
      1. ຖ້າຄ່າໂມດູນແມ່ນ 0, ດັ່ງນັ້ນສາຍສະເພາະນີ້ແມ່ນຂອງພວກເຮົາ ຄໍາຕອບທີ່ຕ້ອງການ.
      2. ອີກຢ່າງ ໜຶ່ງ, ໃຫ້ກວດເບິ່ງວ່າຄ່າ modular ມີຢູ່ໃນຊຸດຫຼືບໍ່.
  5. ຖ້າວ່າຄ່າໂມດູນນັ້ນບໍ່ມີຢູ່ໃນຊຸດ hash, ຫຼັງຈາກນັ້ນໃຫ້ຕື່ມໃສ່ '0' ແລະ '1' ໃສ່ກັບ (ສຳ ເນົາທີ່ແຕກຕ່າງກັນຂອງ) ສະຕິງ.
  6. ຕື່ມສອງເຊືອກເຫຼົ່ານີ້ທີ່ໄດ້ຮັບຫຼັງຈາກການເພີ່ມ '0' ແລະ '1' ເຂົ້າໄປໃນແຖວ ສຳ ລັບການແລກປ່ຽນ BFS.
  7. ເຮັດຊ້ ຳ ອີກຂັ້ນຕອນ 4,5 ແລະ 6 ຈົນກ່ວາຕົວເລກຖານສອງຂອງ ຈຳ ນວນທົດສະນິຍົມປ້ອນເຂົ້າ.

ສູດການຄິດໄລ່ແມ່ນຢູ່ຂ້າງລຸ່ມນີ້:

ຊອກຫາຖານສອງຕົວເລກທີ່ນ້ອຍທີ່ສຸດໃນບັນດາຕົວເລກທີ່ທ່ານໃຫ້

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາຖານສອງທີ່ນ້ອຍທີ່ສຸດຂອງຫລາຍໂຕຂອງຕົວເລກທີ່ໃຫ້

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

/* finds remainder when num is divided by N */
int mod(string num, int N)
{
    int value = 0;
    for(int i=0;i<num.length();i++)
    {
        value = 10*value + int(num[i] - '0');
        value %= N;
    }
    
    return value;
}

/* produces smallest binary digit multiple of given integer */
string smallestBinaryMultiple(int N)
{
    queue <string> q;
    unordered_set <int> us;
    
    string num = "1";
    q.push(num);
    
    /* BFS traversal */
    while(!q.empty())
    {
        string top = q.front(); q.pop();
        
        int modulus = mod(top,N);
        
        if(modulus == 0)
        return top;
        
        if(us.find(modulus) == us.end())
        {
            us.insert(modulus);
            q.push(top+"0");
            q.push(top+"1");
        }
    }
}

int main()
{
    int N = 37;
    cout<<smallestBinaryMultiple(N)<<endl;
    return 0;
}
111

ລະຫັດ Java ເພື່ອຊອກຫາຖານຂໍ້ມູນຖານສອງຕົວເລກທີ່ນ້ອຍທີ່ສຸດໃນບັນດາຕົວເລກທີ່ທ່ານໃຫ້

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* finds remainder when num is divided by N */
    static int mod(StringBuffer num, int N)
    {
        int value = 0;
        for(int i=0;i<num.length();i++)
        {
            value = 10*value + num.charAt(i) - '0';
            value %= N;
        }
        
        return value;
    }
    
    /* produces smallest binary digit multiple of given integer */
    static StringBuffer smallestBinaryMultiple(int N)
    {
        Queue <StringBuffer> q = new LinkedList<>();
        HashSet <Integer> us = new HashSet<Integer>();
        
        StringBuffer num = new StringBuffer("1");
        q.add(num);
        
        /* BFS traversal */
        while(!q.isEmpty())
        {
            StringBuffer top = q.poll();
            
            int modulus = mod(top,N);
            
            if(modulus == 0)
            return top;
            
            if(!us.contains(modulus))
            {
                us.add(modulus);
                
                StringBuffer appendZero = new StringBuffer(top);
                appendZero.append('0');
                
                StringBuffer appendOne = new StringBuffer(top);
                appendOne.append('1');
                
                q.add(appendZero);
                q.add(appendOne);
            }
        }
        
        return num;
    }

  public static void main (String[] args) 
  {
      int N = 37;
        System.out.println(smallestBinaryMultiple(N));
  }
}
111

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

T (n) = O (V + E), ຄວາມສັບສົນເວລາແມ່ນເທົ່າກັບ ຈຳ ນວນອົງປະກອບທີ່ພວກເຮົາມາພົບກັນກ່ອນທີ່ຈະຮອດຜົນທີ່ຕ້ອງການ.

ຄວາມສັບສົນໃນອະວະກາດ

A (n) = O (V), ຄວາມສັບສົນໃນອະວະກາດຍັງຂື້ນກັບຄວາມເທົ່າທຽມກັນ. ຈຳ ນວນອົງປະກອບທີ່ພວກເຮົາພົບເຫັນກ່ອນທີ່ຈະມາເຖິງຜົນທີ່ຕ້ອງການ.

ສະນັ້ນມັນຍາກທີ່ຈະຄິດໄລ່ ຈຳ ນວນເສັ້ນທີ່ ກຳ ລັງຈະມີຢູ່ໃນກາຟກ່ອນທີ່ຈະບັນລຸຜົນທີ່ຕ້ອງການ.

V = ຈຳ ນວນຂອງຂໍ້

E = ຂອບໃນກາຟ