Bir massivdə tək dəfə baş verən ədədi tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon o9 həlləri Snapdeal TCS
Geyim Bitwise-XOR HashingBaxılıb 923

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Verilmiş bir array müsbət tam ədədi. Bütün ədədlər tək sayda baş verən bir rəqəm xaricində hətta bir neçə dəfə baş verir. Bir massivdə tək sayda baş verən ədədi tapmaq məcburiyyətindəyik.

misal

Input

1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6

Buraxılış

4

Tək nömrələrdə baş verən ədədə görə 1 yanaşma

Bir sıra içərisində tək sayda meydana gələn ədədi tapmaq üçün XOR əməliyyatı anlayışından istifadə edirik.

Bildiyimiz kimi

A xor A = 0    ----- Mülkiyyət 1

yəni iki oxşar elementin xoru sıfırdır.

Həmçinin,

A xor 0 = A  -----Mülkiyyət 2

yəni sıfır olan hər hansı bir elementin xor eyni ədədi verir.

Beləliklə alqoritmimiz olacaq,

Alqoritm

1. İlk elementdən başlayın və massivin son elementinə qədər keçin. Bir sıra bütün elementlərin XOR həyata keçirir.

2. Sayı EVEN dəfələrlə baş verərsə, 1 nömrəli nöqtədən Sıfır olacaqdır [1 xassəsinə görə]

3. 1 saylı nöqtədən gələn XOR, tək sayda baş verərsə, ədədə bərabər olacaqdır [2 xüsusiyyətinə görə]

Həyata keçirilməsi

C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  cin>>a[i];
  //initialize the value as first element
  int val = a[0];
  for(int i=1;i<n;i++)
  {
    //XOR of each element so that we can find the number occurring odd number of times
    val = val^a[i];
  }
  cout<<val<<endl;
  return 0;
}

Java Proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        //initialize the value as first element
        int val = arr[0];
        for(int i=1;i<n;i++)
        {
          //XOR of each element so that we can find the number occurring odd number of times
          val = val^arr[i];
        }
        System.out.println(val);
    }
}
5
13 5 3 2 1
8

Qərib Zamanların Sayı Üçün Baş verən Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (N)

Kosmik Mürəkkəblik: O (1)

Tək nömrələrdə baş verən ədədə görə 2 yanaşma 

Bir Hash və ya Xəritə bir sıra elementləri əlavə edin.

Alqoritm

1. Hash və ya Map-də dəyərləri əlavə edin

2. Kimi bir sıra elementi edin açar və elementlərin meydana gəlmə sayı dəyər açarın.

3. Bir sıra bütün elementlərini əlavə etdikdən sonra xəritələri tarayın dəyər və harada tək sayla bir rəqəm alsaq, o zaman açar cavabdır.

Həyata keçirilməsi

C ++ Proqramı 

#include <bits/stdc++.h>
using namespace std;
//map to store 2 int values where first one is for the array element and second one for its count
map<int,int> M;
map<int,int>::iterator it;
int main()
{
  int size;
  cin>>size;
  int arr[size];
  for(int i=0;i<size;i++)
  cin>>arr[i];
  for(int i=0;i<size;i++)
  {
    it = M.find(arr[i]);
    
    // if the number is not present in the map then add it by making its count as 1
    if(it == M.end())
    {
      M.insert(make_pair(arr[i],1));
    }
    else  //if the number is present then simply increase its count by 1
    {
      pair<int,int> p = *it;
      M.erase(it);
      
      //p.second+1 is done for increasing the count by 1
      M.insert(make_pair(p.first,p.second+1));
    }
  }
  
  for(it = M.begin(); it != M.end(); it++)
  {
    //check for odd as if remainder is 1 then if evaluates to true
    if((it->second) % 2 )
    {
      cout<<it->first<<endl;
      return 0;
    }
  }  
  return 0;
}

Java Proqramı

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++)
        {
            int temp = m.get(arr[i])==null? 1: m.get(arr[i])+1;
            m.put(arr[i], temp);
        }
        for (Integer i : m.keySet()) 
        {
            int x = m.get(i);
            if(x%2==1)
            {
                System.out.println(i);
                return;
            }
        }
    }
}
5
1 2 2 2 1
2

Qərib Zamanların Sayı Üçün Baş verən Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (N)

Kosmik Mürəkkəblik: O (N)

Tək nömrələrdə baş verən ədədə görə 3 yanaşma

Son və ən asan düşünülən həll, bütün massivi GÜÇLƏMƏKdir.

Alqoritm

1. Dizidən bir element götürün.

2. Dizinin başlanğıcından sonuna qədər bir döngə aparın və # 1 nöqtəsində götürülmüş elementlə qarşılaşdığımız zaman sayını artırmağa davam edin.

3. 2-ci nöqtədəki say təkdirsə, cavabı alarıq və ya bir sıra növbəti elementləri üçün taramaya davam edirik.

Həyata keçirilməsi

C ++ Proqramı 

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int size; cin>>size;
  int arr[size];for(int i=0;i<size;i++) cin>>arr[i];
  //select each element as reference
  for(int i=0;i<size;i++)
  {
    int count_of_element = 0;
    for(int j=0;j<size;j++)
    {
      //if the number is same as the reference number
      if(arr[j] == arr[i])
        count_of_element++;
    }
    
    //check for odd as if remainder is 1 then if evaluates to true
    if(count_of_element % 2)
    {
      cout << arr[i] <<endl;
      return 0;
    }
  }
  
  return 0;
}

Java Proqramı

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        //select each element as reference
        for(int i=0;i<n;i++)
        {
          int count_of_element = 0;
          for(int j=0;j<n;j++)
          {
            //if the number is same as the reference number
            if(arr[j] == arr[i])
              count_of_element++;
          }
          //check for odd as if remainder is 1 then if evaluates to true
          if(count_of_element % 2==1)
          {
            System.out.println(arr[i]);
            return;
          }
        }
    }
}
6
1 2 3 2 1 2
2

Qərib Zamanların Sayı Üçün Baş verən Mürəkkəblik Analizi

Zamanın mürəkkəbliyi: O (N * N)

Kosmik Mürəkkəblik: O (1)

References

Crack Sistemi Dizayn Müsahibələri
Translate »